题目描述
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
示例 1：
- 输入：n = 4, connections = [[0,1],[0,2],[1,2]]
- 输出：1
- 解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：
- 输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
- 输出：2
示例 3：
- 输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
- 输出：-1
- 解释：线缆数量不足。
示例 4：
- 输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
- 输出：0
提示：
1 <= n <= 10^51 <= connections.length <= min(n*(n-1)/2, 10^5)connections[i].length == 20 <= connections[i][0], connections[i][1] < nconnections[i][0] != connections[i][1]- 没有重复的连接。
- 两台计算机不会通过多条线缆连接。
解法一：并查集
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
type UnionFind struct {
parent []int
rank []int
}
func NewUnionFind(n int) *UnionFind {
uf := &UnionFind{parent: make([]int, n), rank: make([]int, n)}
for i := 0; i < n; i++ {
uf.parent[i] = i
uf.rank[i] = 1
}
return uf
}
func (uf *UnionFind) Find(i int) int {
if uf.parent[i] != i {
uf.parent[i] = uf.Find(uf.parent[i])
}
return uf.parent[i]
}
// Merge 合并 i 所在集合和 j 所在集合，返回 i 和 j 是否在同一个集合中
func (uf *UnionFind) Merge(i, j int) bool {
iF, jF := uf.Find(i), uf.Find(j)
if iF != jF {
// 如果 i 和 j 不在同一个集合
if uf.rank[jF] >= uf.rank[iF] {
uf.parent[iF] = jF
} else {
uf.parent[jF] = iF
}
if uf.rank[jF] == uf.rank[iF] {
uf.rank[jF]++
}
return false
}
return true
}
// Count 返回有几个互不相交的集合
func (uf *UnionFind) Count() int {
ans := 0
for i := 0; i < len(uf.parent); i++ {
if uf.parent[i] == i {
ans++
}
}
return ans
}
func makeConnected(n int, connections [][]int) int {
uf := NewUnionFind(n)
// 冗余的导线数量
lines := 0
for _, connection := range connections {
u, v := connection[0], connection[1]
if uf.Merge(u, v) {
// 如果 u 和 v 在使用当前导线连接前就已经处在同一个网络，则当前导线是冗余导线
lines++
}
}
// m 个不连通的网络至少需要 m-1 根导线才能使它们连通
if lines < uf.Count()-1 {
return -1
}
return uf.Count() - 1
}
|
