class Solution { int ans ; public: int find(int u,vector<int>& parent) { if(u == parent[u]) return u; else return parent[u] = find(parent[u],parent); } void combine (int u, int v,vector<int>& size,vector<int>& parent) { u = find(u,parent); v = find(v,parent); if(u == v) return; else { ans--; if(size[u] > size[v]) { parent[v] = u; size[u] += size[v]; } else { parent[u] = v; size[v] += size[u]; } } } int findCircleNum(vector<vector<int>>& isConnected) { int n = isConnected.size(); vector<int> parent(n+1,0); vector<int> size(n+1,1); size[0]=0; for(int i=1;i<=n;i++) parent[i]=i; ans =n; for(int i=0;i<n;i++) for(int j=0;j<isConnected[0].size();j++) { if(i!=j&&isConnected[i][j]==1) { combine(i+1,j+1,size,parent); } } return ans; } };
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter