DSU
Sat Jun 19 2021 06:06:18 GMT+0000 (Coordinated Universal Time)
Saved by
@Randumkeng
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;
}
};
content_copyCOPY
disjoint set union with path compression and union by size
https://leetcode.com/problems/number-of-provinces/submissions/
Comments