题解 | #城市群数量#

class Solution {
public:
    int find(vector<int> &father,int i){
        if(father[i]==i) return i;
        else return father[i]=find(father,father[i]);//记忆化搜索
    }//找到节点i的根节点
    int citys(vector<vector<int> >& m) {
        int n=m.size();
        vector<int> father(n,0);
        for(int i=0;i<n;i++){
            father[i]=i;//定义初始每个节点的父节点是自己
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(m[i][j]==1&&find(father,i)!=find(father,j)){
                    father[find(father,j)]=find(father,i);
                    //注意这里的逻辑是把j的根节点指向i的根节点，不是只移动父节点
                }
            }
        }
        vector<int> a(n,0);
        for(int k=0;k<n;k++){
            a[find(father,k)]=1;//
        }
        int ans=0;
        for(int k=0;k<n;k++){
            ans+=a[k];
        }
        return ans;
    }
};