05 August 2008
有 n 台计算机，编号从 0 到 n - 1，通过以太网电缆连接形成一个网络，其中 connections[i] = [ai, bi] 表示计算机 ai 和 bi 之间的连接。任何计算机都可以通过网络直接或间接访问任何其他计算机。
您将获得初始计算机网络连接。您可以在两台直接连接的计算机之间提取某些电缆，并将它们放置在任何一对断开连接的计算机之间以使它们直接连接。
返回为使所有计算机连接所需执行此操作的最少次数。如果不可能，则返回-1。
Union Find
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public int makeConnected(int n, int[][] connections) {
if (connections.length < n - 1)
return -1;
int[] parent = new int[n];
int count = 0;
for (int i = 0; i < n; i++)
parent[i] = i;
for (int[] connection : connections) {
Union(parent, connection[0], connection[1]);
}
for (int i = 0; i < n; i++) {
if (parent[i] == i)
count++;
}
return count - 1;
}
public static int find(int[] parent, int i) {
if (parent[i] == i) return i;
return find(parent, parent[i]);
}
public static void Union(int[] parent, int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
}