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

//并查集
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的根节点//根节点存在parent[x] = 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);//返回p的根节点
        int rootq = Find(q);
        if (rootp == rootq)//如果两者根节点相同，则在同一个集合里面，跳过
            return ;
        //根节点不同，但是由于p，q为连接的，故将p的集合作为子节点连接在q下面：rootp->rootq
        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();
    }
};

并查集的思想在于，最初初始化一个n的父节点为parent[n]并使其指向自身，然后通过外界条件不断吸纳与自身相连的元素成为一棵树，并使用parent[n]记录之间关系。

并查集查找自身的根节点比较方便。