547. 省份数量(leetcode)

https://leetcode.cn/problems/number-of-provinces/

并查集模版题

class Solution {

    int[] p;

    void init(int n)
    {
        p=new int[n];
        for(int i=0;i<n;i++)p[i]=i;
    }

    int find(int x)
    {
        return x==p[x] ? x:(p[x]=find(p[x]));
    }

    void union(int x,int y)
    {
        p[find(x)]=find(y);
    }

    public int findCircleNum(int[][] isConnected) {
        int res=0;
        init(isConnected.length);
        for(int i=0;i<isConnected.length;i++)
            for(int j=0;j<isConnected[i].length;j++)
            {
                if(isConnected[i][j]==1)union(i,j);
            }
        // 查询并查集数量
        for(int i=0;i<isConnected.length;i++)
        {
            if(find(i)==i)res++;
        }
        return res;
        
    }
}