Untitled
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