并查集练习——省份数量

力扣原题链接：省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnectedi = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnectedi = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnectedi 为 1 或 0
isConnectedi == 1
isConnectedi == isConnectedj

package com.harrison.class10;

/**
 * @author Harrison
 * @create 2022-03-19-13:11
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code02_FriendCircles {
    // https://leetcode.com/problems/friend-circles/
    public static class UnionFind{
        // parent[i]=k i的父亲是K
        public int[] parent;
        // size[i]=k 如果i是代表结点，size[i]才有意义，否则无意义
        // i所在的集合大小是k
        public int[] size;
        // 辅助结构
        public int[] help;
        // 一共有多少个集合
        public int sets;

        public UnionFind(int N){
            parent=new int[N];
            size=new int[N];
            help=new int[N];
            sets=N;
            for(int i=0; i<N; i++){
                parent[i]=i;
                size[i]=i;
            }
        }

        // 从i开始往上，往上到不能再往上，就是代表结点，返回
        // 这个过程要做路径压缩
        public int find(int i){
            int hi=0;
            while (i!=parent[i]){
                help[hi++]=i;
                i=parent[i];
            }
            for(hi--; hi>=0; hi--){
                parent[help[hi]]=i;
            }
            return i;
        }

        public void union(int i,int j){
            int f1=find(i);
            int f2=find(j);
            if(f1!=f2){
                if(size[f1]>=size[f2]){
                    size[f1]+=size[f2];
                    parent[f2]=f1;
                }else{
                    size[f2]+=size[f1];
                    parent[f1]=f2;
                }
                sets--;
            }
        }

        public int sets(){
            return sets;
        }
    }

    public static int findCircleNum(int[][] isConnected){
        int N=isConnected.length;
        // {0} {1} {2} {3}...{N-1}
        UnionFind unionFind=new UnionFind(N);
        for(int i=0; i<N; i++){
            for(int j=i+1; j<N; j++){
                if(isConnected[i][j]==1){// i和j互相认识
                    unionFind.union(i,j);
                }
            }
        }
        return unionFind.sets;
    }
}