题解 | #城市群数量#并查集 C++

//并查集
class UnionFind{
    public:
        vector<int> parent;//记录父节点
        int cnt;//连通分量
        UnionFind(int n){
            this->cnt = n;
            this->parent.resize(n);
            for(int i=0;i<n;++i){
                parent[i] = i;//初始父节点指向自己
            }

        }
        //找到x的根节点
        int Find(int x){
            while(parent[x]!=x){
                x = parent[x];
            }
            return x;
        }
        //连接p和q
        void Union(int p,int q){
            int rootp = Find(p);
            int rootq = Find(q);
            if(rootp==rootq)
                return ;
            parent[rootp] = rootq;
            cnt--;
        }
        //返回连通分量
        int Connect(){
            return cnt;
        }

};

class Solution {
public:
    int citys(vector<vector<int> >& m) {
        // write code here
        int n = m.size();
        if(n==1)
            return 1;
        UnionFind uf(n);
        //遍历邻接矩阵
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(i==j)
                    continue;
                if(m[i][j]==1)
                    uf.Union(i, j);
            }
        }

        return uf.Connect();
    }
};