547. 朋友圈

547. 朋友圈

也可以dfs，就跟搜岛屿啥的一样，不过这个题用dfs没有充分利用题上条件...本质就是考察并查集

并查集

class Solution {
public:
    vector<int>p;
    int find(int x){
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    }
    int findCircleNum(vector<vector<int>>& M) {
        int n=M.size();
        p=vector<int>(n);
        for(int i=0;i<p.size();i++)p[i]=i;
        
        for(int i=0;i<M.size();i++){
            for(int j=0;j<M[0].size();j++){
                if(M[i][j]){
                    int rooti=find(i),rootj=find(j);
                    if(rooti!=rootj){
                        p[rooti]=rootj;
                    }
                }
            }
        }
        
        int res=0;
        // 找出有几个集合
        for(int i=0;i<p.size();i++)
            if(p[i]==i)
                res++;
        
        return res;
        
    }
};