Problem Link: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=734
Note: This problem is a straightforward Union Find problem but one might struggle with the input criteria; almost like UVA 459. 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;
// getchar(); //Taking one blank line
// getchar();
// cin.ignore();
// cin.ignore(); //can use this instead of getchar();
while(t--)
{
int node;
cin>>node;
vector<int> root(node+1), ranking(node+1);
for(int i=0; i<node; i++)
{
root[i]=i;
ranking[i]=1;
}
string s;
int yes=0, no=0;
getchar(); //Flushig the '\n' character from the input buffer which was there for using cin
while(getline(cin,s) && s.size())
{
char ch=s[0];
size_t found=s.find(" ", 2);
string num1=s.substr(2, found-2);
int x=stoi(num1);
string num2=s.substr(found+1);
int y=stoi(num2);
if(ch=='c') Union(x, y, root, ranking);
else
{
if(Find(x, root)==Find(y, root)) yes++;
else no++;
}
}
cout<<yes<<","<<no<<endl;
if(t) cout<<endl;
}
return 0;
}
One thought on “UVA 793 – Network Connections”