#1319

Number of Operations to Make Network Connected

specialist · 610 · lc medium +29 · verified · 66.2% accepted · 5,574 likes · top 71%

Description

You have n computers numbered 0 through n - 1 connected by cables, where connections[i] = [ai, bi] indicates a direct link between computers ai and bi.

You may remove a cable between two directly connected computers and reinstall it to link any other pair. Return the minimum number of such cable moves to make all computers reachable from one another, or -1 if it is impossible.

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]

Output: 1

Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

Example 2:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]

Output: 2

Example 3:

Input: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]

Output: -1

Explanation: There are not enough cables.

Code

1

2

3

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int: