【并查集】547. 省份数量_java并查集求省份数数量

class Solution {
    public int findCircleNum(int[][] isConnected) {
        UnionFind uf = new UnionFind(isConnected.length);

        for(int i = 0 ; i < isConnected.length ; i++){
            for(int j = i + 1 ; j < isConnected[0].length ; j++){
                //如果城市相连都为1 , 用并查集把他们相连
                if(isConnected[i][j] == 1) uf.union(i,j);
            }
        }

        return uf.getCount();
    }

    public class UnionFind{
        private int [] parent;
        private int [] size;
        private int [] help;
        private int count;

        public UnionFind(int n){
            //头节点初始化为自己
            parent = new int[n];
            for(int i = 0 ; i < n ; i++) parent[i] = i;
            //省份初始城市数量都设为1
            size = new int[n];
            Arrays.fill(size,1);
            //省份初始数量n
            count = n;
            help = new int[n];
        }

        public void union(int n , int m){
           int nfather = findFather(n);
           int mfather = findFather(m);
           if(nfather == mfather) return;
           int nSize = size[nfather];
           int mSize = size[mfather];
           //找到子节点更多的节点
           int bigfather = nSize >= mSize ? nfather : mfather;
           //找到子节点更少的节点
           int smallfather = bigfather == nfather ? mfather : nfather;
           //子节点更少的节点认子节点更多的节点为父节点
           parent[smallfather] = bigfather;
           //子节点更多的节点重新计算数量
           size[bigfather] += size[smallfather];
           //子节点更多的节点吞并了子节点少的节点,count--
           count--;
        }

        public int findFather(int n){
            int cur = n;
            int index = 0;
            //父节点不是自己
            while(cur != parent[cur]){
                help[index++] = cur;
                cur = parent[cur];
            }
            //找父节点路径上的节点和父节点连接
            //这个过程要做路径压缩
            for(int i = 0 ; i < index ; i++){
                parent[help[i]] = cur;
            }
            return cur;
        }

        public int getCount(){
            return count;
        }
    }
}
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
68
69
70
71