LeetCode 1319 - Number of Operations to Make Network Connected

LeetCode Problem 1319

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

Problem Understanding

This problem models a computer network as an undirected graph. Each computer is a node, and each ethernet cable is an edge connecting two nodes. The goal is to determine the minimum number of cable rewirings needed to make the entire network fully connected.

A network is considered fully connected if every computer can reach every other computer, either directly or through intermediate computers. The important detail is that we are allowed to remove an existing cable and reconnect it somewhere else. In other words, if there are redundant connections inside one connected component, those cables can potentially be reused to connect separate disconnected components.

The input consists of:

• n, the number of computers labeled from 0 to n - 1
• connections, where each entry [a, b] represents a bidirectional cable between computers a and b

The output should be the minimum number of cable moves required to connect the entire network. If it is impossible, we return -1.

The constraints are important because they guide the algorithm choice:

• n can be as large as 10^5
• The number of connections can also be up to 10^5

This immediately rules out expensive graph algorithms with quadratic complexity. We need a near linear solution.

There is also a key graph theory observation hidden in the problem. A connected graph with n nodes requires at least n - 1 edges. If the total number of cables is less than n - 1, then it is mathematically impossible to connect all computers, regardless of how cables are rearranged.

Several edge cases are important:

• A network with too few cables, such as n = 6 and only 4 connections
• Multiple disconnected components
• Already connected networks
• Isolated nodes with no direct connections
• Networks containing redundant cycles, where some edges can safely be removed and reused

The problem guarantees there are no duplicate connections and no self loops, which simplifies the implementation.

Approaches

Brute Force Approach

A brute force strategy would attempt to simulate cable removals and reconnections between disconnected components. One could repeatedly search for redundant edges, remove one, and reconnect two disconnected groups until either the graph becomes connected or no spare cables remain.

To determine connectivity after every operation, we might run DFS or BFS repeatedly across the graph. Since each operation changes the graph structure, connectivity checks would have to be recomputed many times.

This approach is correct because it explicitly models the allowed operations. However, it is extremely inefficient. Repeated graph traversals combined with repeated rewiring attempts could easily lead to quadratic or worse complexity, which is too slow for 10^5 nodes.

Optimal Approach

The key insight is that we do not actually need to simulate cable movement.

Suppose the network has k connected components. To connect all components into one connected network, we need exactly k - 1 cables. This is because each operation can merge two components together.

Now consider spare cables. Any cycle in a component contains redundant edges. Those redundant edges can be extracted and reused elsewhere.

Instead of explicitly counting redundant edges, we can use a simpler mathematical condition:

• A connected graph with n nodes requires at least n - 1 edges.
• If the graph already has at least n - 1 total edges, then there are enough cables overall to connect all components.

So the algorithm becomes:

1. Check whether the total number of connections is at least n - 1
2. Count the number of connected components
3. Return components - 1

We can efficiently count connected components using either:

• DFS/BFS
• Union-Find

Union-Find is especially efficient for large graphs because it supports near constant time merging and lookup operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) or worse	O(n)	Repeatedly simulates rewiring and connectivity checks
Optimal	O(n + m)	O(n)	Counts connected components using Union-Find or DFS

Here, m represents the number of connections.

Algorithm Walkthrough

Union-Find Based Algorithm

1. First, check whether the number of cables is sufficient.

A connected graph with n nodes requires at least n - 1 edges. If len(connections) < n - 1, immediately return -1. 2. Initialize a Union-Find data structure.

Each computer initially belongs to its own separate component. We create:

• A parent array where each node is its own parent
• A rank or size array to optimize unions

3. Process every connection.

For each edge [a, b], perform a union operation between a and b.

If the two computers already belong to the same component, the edge is redundant. We do not actually need to store redundant edges separately because the edge count condition already guarantees enough spare cables exist. 4. Count connected components.

Every unique root in the Union-Find structure represents one connected component. 5. Compute the answer.

If there are k connected components, we need exactly k - 1 operations to connect them all.

Why it works

Each operation can connect exactly two disconnected components. Therefore, reducing k components into one connected network always requires k - 1 operations.

The graph must also contain enough total cables. Since a connected graph with n nodes requires at least n - 1 edges, having fewer edges makes the task impossible.

Union-Find correctly groups all nodes belonging to the same connected component, so counting components gives the exact number of required merges.

Python Solution

from typing import List

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        parent = list(range(n))
        rank = [0] * n

        def find(node: int) -> int:
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]

        def union(a: int, b: int) -> bool:
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return False

            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1

            return True

        components = n

        for a, b in connections:
            if union(a, b):
                components -= 1

        return components - 1

The implementation begins with the critical feasibility check. If the number of connections is smaller than n - 1, the function immediately returns -1 because a connected graph cannot exist with too few edges.

The parent array stores the representative parent of each node. Initially, every node is its own parent because each computer starts as an independent component.

The find function performs path compression. Whenever we search for the root of a node, we recursively compress the path so future lookups become faster.

The union function merges two components. If both nodes already share the same root, the edge is redundant and no merge occurs. Otherwise, union by rank keeps the tree shallow, improving efficiency.

The variable components starts at n because every node is initially disconnected. Every successful union reduces the component count by one.

Finally, the answer is components - 1, representing the number of operations needed to merge all remaining disconnected groups.

Go Solution

func makeConnected(n int, connections [][]int) int {
	if len(connections) < n-1 {
		return -1
	}

	parent := make([]int, n)
	rank := make([]int, n)

	for i := 0; i < n; i++ {
		parent[i] = i
	}

	var find func(int) int

	find = func(node int) int {
		if parent[node] != node {
			parent[node] = find(parent[node])
		}
		return parent[node]
	}

	union := func(a int, b int) bool {
		rootA := find(a)
		rootB := find(b)

		if rootA == rootB {
			return false
		}

		if rank[rootA] < rank[rootB] {
			parent[rootA] = rootB
		} else if rank[rootA] > rank[rootB] {
			parent[rootB] = rootA
		} else {
			parent[rootB] = rootA
			rank[rootA]++
		}

		return true
	}

	components := n

	for _, connection := range connections {
		if union(connection[0], connection[1]) {
			components--
		}
	}

	return components - 1
}

The Go implementation follows the same algorithmic structure as the Python version. Slices are used for the parent and rank arrays. Recursive path compression is implemented using a closure for find.

Go does not support nested named functions in the same way as Python, so closures are used for both find and union.

Integer overflow is not a concern because all values remain well within Go's standard integer range.

Worked Examples

Example 1

Input:

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

Initial state:

Computer	Parent
0	0
1	1
2	2
3	3

Initial components: 4

Process connection [0,1]

• Union succeeds
• Components become 3

Computer	Parent
0	0
1	0
2	2
3	3

Process connection [0,2]

• Union succeeds
• Components become 2

Computer	Parent
0	0
1	0
2	0
3	3

Process connection [1,2]

• Both already belong to root 0
• Redundant edge
• Components remain 2

Final result:

components - 1 = 2 - 1 = 1

Answer: 1

Example 2

Input:

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

Total edges = 5

Since n - 1 = 5, enough cables exist.

Union operations produce:

• Component {0,1,2,3}
• Component {4}
• Component {5}

Total components = 3

Required operations:

3 - 1 = 2

Answer: 2

Example 3

Input:

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

Total edges = 4

A connected graph with 6 nodes requires at least 5 edges.

Since:

4 < 5

it is impossible to connect the network.

Answer: -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Union-Find operations are nearly constant time
Space	O(n)	Parent and rank arrays store one entry per node

The Union-Find data structure uses path compression and union by rank, which makes each operation effectively amortized constant time, more precisely O(α(n)), where α is the inverse Ackermann function.

Since we process every connection exactly once, the total runtime is linear relative to the size of the input.

Test Cases

from typing import List

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections) < n - 1:
            return -1

        parent = list(range(n))
        rank = [0] * n

        def find(node):
            if parent[node] != node:
                parent[node] = find(parent[node])
            return parent[node]

        def union(a, b):
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return False

            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1

            return True

        components = n

        for a, b in connections:
            if union(a, b):
                components -= 1

        return components - 1

solution = Solution()

assert solution.makeConnected(
    4,
    [[0,1],[0,2],[1,2]]
) == 1  # Example 1

assert solution.makeConnected(
    6,
    [[0,1],[0,2],[0,3],[1,2],[1,3]]
) == 2  # Example 2

assert solution.makeConnected(
    6,
    [[0,1],[0,2],[0,3],[1,2]]
) == -1  # Example 3, insufficient cables

assert solution.makeConnected(
    1,
    []
) == 0  # Single computer already connected

assert solution.makeConnected(
    2,
    [[0,1]]
) == 0  # Already fully connected

assert solution.makeConnected(
    3,
    [[0,1]]
) == -1  # Not enough edges

assert solution.makeConnected(
    5,
    [[0,1],[0,2],[3,4],[2,1]]
) == 1  # One redundant edge available

assert solution.makeConnected(
    5,
    [[0,1],[1,2],[2,3],[3,4]]
) == 0  # Tree structure already connected

assert solution.makeConnected(
    5,
    [[0,1],[1,2],[2,0],[3,4]]
) == 1  # One cycle creates reusable cable

assert solution.makeConnected(
    10,
    [[0,1],[1,2],[2,3],[3,4],[4,0],
     [5,6],[6,7],[7,8],[8,9],[9,5]]
) == 1  # Two large cyclic components

Test	Why
n=4, [[0,1],[0,2],[1,2]]	Validates basic redundant cable usage
n=6, [[0,1],[0,2],[0,3],[1,2],[1,3]]	Tests multiple disconnected components
n=6, [[0,1],[0,2],[0,3],[1,2]]	Validates insufficient cable detection
n=1, []	Smallest possible input
n=2, [[0,1]]	Already connected minimal graph
n=3, [[0,1]]	Too few edges
n=5, [[0,1],[0,2],[3,4],[2,1]]	Uses a redundant cycle edge
n=5, linear chain	Tests already connected tree
n=5, one cycle plus one component	Verifies reusable cycle edge
n=10, two cyclic components	Larger disconnected cyclic graph

Edge Cases

Insufficient Total Cables

One of the most important edge cases occurs when the graph simply does not contain enough edges overall. A connected graph with n nodes must contain at least n - 1 edges. If this condition fails, no amount of rewiring can make the graph connected.

For example:

n = 6
connections = 4 edges

Even if every edge were perfectly placed, six nodes cannot form a connected graph with only four edges. The implementation handles this immediately with:

if len(connections) < n - 1:
    return -1

This early exit avoids unnecessary computation.

Already Connected Network

Another important case is when the graph is already fully connected. In this situation, the answer should be 0 because no rewiring operations are needed.

For example:

n = 5
connections = [[0,1],[1,2],[2,3],[3,4]]

The Union-Find structure merges all nodes into one component. Since the final component count becomes 1, the algorithm returns:

1 - 1 = 0

Multiple Isolated Components

A graph may contain several disconnected groups along with isolated nodes. These cases can easily cause bugs if component counting is incorrect.

For example:

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

Here we have four components:

• {0,1}
• {2,3}
• {4}
• {5}

The algorithm correctly counts all components through Union-Find root tracking. Since four components require three merges, the algorithm returns:

4 - 1 = 3

provided enough spare cables exist.