Leetcode 1319. 连通网络的操作次数（Java实现 超详细注释！）

Leetcode 1319. 连通网络的操作次数

并查集+HashSet，这道题可以作为并查集的入门题，只要理解了并查集的原理，这道题在逻辑上是比较好理解的！加了详细的注释，方便日后复习，也希望能帮到其他小伙伴，如有错误，欢迎指正！

Java实现：

class Solution {
    public int makeConnected(int n, int[][] connections) {
        // 我们先判断是否可能使所有计算机都连通，所有都连通的必要条件为线缆的条数至少有n-1条，如果不满足直接返回-1
        if (connections.length < n - 1){
            return -1;
        }
        // 初始化一个并查集
        DisjointSetUnion djsu = new DisjointSetUnion(n);
        // 我们使用题目给定的已有连接情况去构建并查集，得到当前n台计算机的连接情况
        for (int i = 0; i < connections.length; i ++){
            djsu.unionSet(connections[i][0],connections[i][1]);
        }
        // 我们用HashSet来存每一台计算机的根节点
        HashSet<Integer> hs = new HashSet<Integer>();
        for (int j = 0; j < n; j++){
            hs.add(djsu.find(j));
        }
        /**可以试想一下，最少的操作数其实就是将未相连的几个根节点相连；
        hs.size()表示未相连的根节点数目，我们至少需要操作hs.size() - 1根线缆才能使所有计算机都连通；*/
        return hs.size() - 1;
        

    }
    // 并查集
    class DisjointSetUnion{
        int[] f;
        public DisjointSetUnion(int n){
            this.f = new int[n];
            for (int i = 0; i < n; i++){
                f[i] = i;
            }
        }
        // 并
        private void unionSet(int x, int y){
            int fx = find(x), fy = find(y);
            if (fx != fy){
                f[fx] = fy;
            }
        }
        // 查
        private int find(int a){
            return f[a] == a ? a : (f[a] = find(f[a]));
        }
    }
}
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