1319. Number of Operations to Make Network Connected #

Problem #

There are n computers numbered from 0 to n-1 connected by ethernet cables connections forming a network where connections[i] = [a, b] represents a connection between computers a and b. Any computer can reach any other computer directly or indirectly through the network.

Given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected. Return the minimum number of times you need to do this in order to make all the computers connected. If it’s not possible, return -1.

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.

Example 4:

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

Constraints:

• 1 <= n <= 10^5
• 1 <= connections.length <= min(n*(n-1)/2, 10^5)
• connections[i].length == 2
• 0 <= connections[i][0], connections[i][1] < n
• connections[i][0] != connections[i][1]
• There are no repeated connections.
• No two computers are connected by more than one cable.

Problem Summary #

Use ethernet cables to connect n computers into a network, with computers numbered from 0 to n-1. The cables are represented by connections, where connections[i] = [a, b] connects computers a and b. Any computer in the network can directly or indirectly access any other computer in the same network. Given the initial wiring connections of this computer network, you can unplug the cable between any two directly connected computers and use it to connect a pair of computers that are not directly connected. Compute and return the minimum number of operations required to make all computers connected. If it is impossible, return -1.

Solution Approach #

• Obviously, the solution idea for this problem is Union-Find. First build the Union-Find structure from each connection. During construction, accumulate redundant connections. For example, if 2 nodes are already connected, then connecting any 2 nodes in this set counts as a redundant connection. All redundant cables can be moved to connect nodes that are not yet connected. Calculate the number of redundant connections, and then based on the total number of sets in the Union-Find structure, the answer can be obtained.
• There are 3 possible answers for this problem. First, all points are in one set, meaning they are all connected; in this case output 0. Second, there are not enough redundant connections to link all points together; in this case output -1. The third case is when they can be connected. To connect m sets, at least m - 1 cables are needed. If the number of redundant connections is greater than m - 1, simply output m - 1.

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

func makeConnected(n int, connections [][]int) int {
	if n-1 > len(connections) {
		return -1
	}
	uf, redundance := template.UnionFind{}, 0
	uf.Init(n)
	for _, connection := range connections {
		if uf.Find(connection[0]) == uf.Find(connection[1]) {
			redundance++
		} else {
			uf.Union(connection[0], connection[1])
		}
	}
	if uf.TotalCount() == 1 || redundance < uf.TotalCount()-1 {
		return 0
	}
	return uf.TotalCount() - 1
}