【并查集】547. 省份数量

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;
        }
    }
}