并查集 | #城市群数量#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param m int整型vector<vector<>>
     * @return int整型
     */
    int citys(vector<vector<int> >& m) {
        // write code here
        int n = m.size();
        initf(n);
        sz.assign(n,1);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int a = m[i][j];
                int x = find(i), y = find(j);
                if ( a && x != y && i != j) {
                    p[x] = y;
                    sz[y] += sz[x];
                }
            }
        }
        int ccnt = 0;
        for(int i=0;i<n;i++) {
            int j =  find(i);
            if(sz[j]>0) {
                ccnt+=1;
                sz[j] = -sz[j];
            }
        }
        return ccnt;

    }
    vector<int> p;
    vector<int> sz; 
    int find(int x) {
        int y = p[x];
        if (y != x)
            return p[x] = find(p[x]);
        return y;
    }
    void initf(int x) {
        p.assign(x , 0);
        for (int i = 0; i < x; i++)
            p[i] = i;
    }

};