Untitled

mail@pastecode.io avatar
unknown
plain_text
15 days ago
1.0 kB
1
Indexable
Never
class Solution {
public:
    vector<int>par;
    vector<int>rank;
    int find(int i){
        if(par[i]!=i){
            par[i]=find(par[i]);
        }
        return par[i];
    }

    void add(int a,int b){
        a=find(a);
        b=find(b);
        if(rank[a]!=rank[b]){
            if(rank[a]<rank[b]){
                par[a]=b;
            }else{
                par[b]=a;
            }
        }
        else{
            par[a]=b;
            rank[b]++;
        }
    }

    int findCircleNum(vector<vector<int>>& con) {
        int n=con.size();
        par=vector<int>(n,0);
        rank=vector<int>(n,0);

        for(int i=0;i<n;i++) {
            par[i]=i;
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(con[i][j]){
                    add(i,j);
                }
            }
        }
        int ans=0;
        for(int i=0;i<par.size();i++){
            if(par[i]==i) ans++;
        }
        return ans;
    }
};
Leave a Comment