Problem Link: https://onlinejudge.org/external/106/10608.pdf
Approach 1: This code is simply using the ranking vector of the Union-Find algorithm when we update the ranking vector by the total number of connected nodes to the root node.
#include <bits/stdc++.h>
using namespace std;
int Find(int x, vector<int> &root)
{
if(x==root[x]) return x;
return root[x]=Find(root[x], root);
}
void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
int rootX=Find(x, root);
int rootY=Find(y, root);
if(rootX!=rootY)
{
if(ranking[rootX]>=ranking[rootY])
{
root[rootY]=rootX;
ranking[rootX]+=ranking[rootY];
}
else
{
root[rootX]=rootY;
ranking[rootY]+=ranking[rootX];
}
}
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector<int> root(n+1), ranking(n+1);
for(int i=1; i<=n; i++)
{
root[i]=i;
ranking[i]=1;
}
for(int i=0; i<m; i++)
{
int x,y;
cin>>x>>y;
Union(x,y, root, ranking);
}
int ans=-1;
for(int i=1; i<=n; i++)
{
ans=max(ranking[i], ans);
}
cout<<ans<<endl;
}
return 0;
}
Approach 2: If the ranking vector is updated by the height of the node, then we’ll have to do something extra in the main function to get the answer to this problem. This is exactly why I prefer the first approach though both of these approaches have the same time complexity.
Here, after establishing the relationship between all the pairs of people, we are implementing the Find function for each of the people. Because as I mentioned in the basic algorithm discussion – here(the “important observation”), after using the Union function for all pairs, our root vector is not fully updated yet.
That’s why we need to run Find() function for each of the nodes to get the actual root node of all the nodes. And in the meantime, we are collecting the number of nodes each root node is containing including itself.
Code:
#include <bits/stdc++.h>
using namespace std;
int Find(int x, vector<int> &root)
{
if(x==root[x]) return x;
return root[x]=Find(root[x], root);
}
void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
int rootX=Find(x, root);
int rootY=Find(y, root);
if(rootX!=rootY)
{
if(ranking[rootX]>ranking[rootY]) root[rootY]=rootX;
else if(ranking[rootY]>ranking[rootX]) root[rootX]=rootY;
else
{
root[rootY]=rootX;
ranking[rootX]++;
}
}
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector<int> root(n+1), ranking(n+1);
for(int i=1; i<=n; i++)
{
root[i]=i;
ranking[i]=1;
}
for(int i=0; i<m; i++)
{
int x,y;
cin>>x>>y;
Union(x,y, root, ranking);
}
int member_count[n+1]={0};
for(int i=1; i<=n; i++)
{
int root_i=Find(i, root); //updating the final root vector
member_count[root_i]++;
}
int ans=-1;
for(int i=1; i<=n; i++)
{
ans=max(member_count[i], ans);
}
cout<<ans<<endl;
}
return 0;
}
Fall out, Codes! 
3 thoughts on “UVa – 10608 – Friends”