leetcodeと調査集547.モーメンツjava

https://leetcode-cn.com/problems/friend-circles/

class Solution {
    int[] p;//parent
    public int findCircleNum(int[][] M) {
        int n = M.length;
        p = new int[n+1];
        for(int i=0; i<n; i++) p[i] = i;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(M[i][j] == 1){
                    int x = find(i); int y = find(j);
                    if(x != y) p[x] = y;
                }
            }
        }
        int res = 0;
        for(int i = 0; i<n; i++){
            if(p[i] == i)
                res++;
        }
        return res;
    }
    public int find(int x){
        if(p[x] != x)
            p[x] = find(p[x]);
        return p[x];
    }
}

前は、王parent配列を生成し、いくつかのparent:for if(p[i]==i)res++を検索します.