leetcode 547. 省份数量

题目链接：https://leetcode.cn/problems/number-of-provinces/
题目描述：

其实就是求联通分量，咱们可以用bfs或者dfs跑，看几遍能跑完就有几个联通分量，也可以使用并查集。

class Solution {
public:
    int bk[205];
    queueq;
    int findCircleNum(vector>& isConnected) {
        int n,m;
        n=isConnected.size();
        m=isConnected[0].size();
        int ans=0;
        for(int i=0;i
            if(bk[i]==0){
                ans++;
                q.push(i);
                bk[i]=1;
            }
            while(q.size()){
                int k=q.front();
                q.pop();
                for(int i=0;i
                    if(isConnected[k][i]&&bk[i]==0){
                        bk[i]=1;
                        q.push(i); 
                    }
                }
            }
        }
        return ans;
    }
};

class Solution {
public:
    int fa[205];
    setp;
    int getf(int q){
    if(fa[q]==q) return q;
    return fa[q]=getf(fa[q]);
    }
    void  mer(int x,int y){
        int newx=getf(x);
        int newy=getf(y);
        if(newx==newy) return ;
        if(newx>newy){
            fa[newy]=newx;
        }else{
            fa[newx]=newy;
        }
    }
    int findCircleNum(vector>& isConnected) {
        int n,m;
        n=isConnected.size();
        m=isConnected[0].size();
        //cout<
            fa[i]=i;
        }
        for(int i=0;i
            for(int j=0;j
                if(isConnected[i][j]) mer(i,j);
            }
        }
        int ans=1;
        for(int i=0;i
            //cout<