Problem Link: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=400
Note: This problem is a straightforward Union Find problem but one might struggle with the input format. Please make sure you understand the concepts of taking string/character input in C++.
And about the input format, we do not have to bother with the blank lines because “std::cin” by nature isn’t bothered with those blank lines. We’ll just have to make sure that we use getchar() before using getline() as there are some “cin” statements before using getline(). Please have a look at the following link for further explanation.
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;
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--)
{
string s;
char ch;
cin>>ch;
int node=ch-'A' + 1;
vector<int> root(node),ranking(node);
for(int i=0; i<node; i++)
{
root[i]=i;
ranking[i]=1;
}
getchar(); //Flushig the '\n' character from the input buffer which was there for using cin
while(getline(cin,s) && s.size())
{
int x=s[0]-'A';
int y=s[1]-'A';
Union(x, y, root, ranking);
}
int ans=0;
for(int i=0; i<node; i++)
{
if(root[i]==i) ans++;
}
cout<<ans<<endl;
if(t) cout<<endl;
}
return 0;
}
Fall out, Codes! 
2 thoughts on “UVA 459 – Graph Connectivity”