793 - Network Connections

/***
Md. Nazmul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<iostream>
#include<cstdio>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<cmath>
#include <iomanip>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size)  for(int i=0 ; i<size ; i++) cin>>array[i]  ;
#define new_line  pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int parent[100001], rank_n[100001];

void makePair(int x)
{
    parent[x] =x;
    rank_n[x] =0;
}

int find_n(int x)
{
    if(parent[x]!=x)
        parent[x] = find_n(parent[x]);
    return parent[x];
}

void makeUnion(int x, int y)
{
    int px = find_n(x);
    int py = find_n(y);

    if(px==py)
        return;
    if(rank_n[px] > rank_n[py])
        parent[py] = px;
    else
    {
        parent[px] = py;
        if(rank_n[px] == rank_n[py])
            rank_n[px]++;
    }
}


int main()
{
    int test,n,u,v,cnt1,cnt2;
    char ch, str[10001];
    sc("%d",&test);

   for(int tc=1 ; tc<=test ; tc++)
    {
        sc("%d",&n);
        memset(parent,0,sizeof(parent));

        for(int i=1 ; i<=n ; i++)
            makePair(i);
        getchar();
        cnt1 = cnt2 =0;
        while(1)
        {
           gets(str);
           if(strcmp(str,"")==0 || feof(stdin))
            break;
           sscanf(str,"%c %d %d",&ch,&u,&v);
           if(ch == 'c')
            makeUnion(u,v);
           else if(ch =='q')
             if(find_n(u) == find_n(v))
                cnt1++;
            else
                cnt2++;
        }
        if(tc!=1)
            pf("\n");
        pf("%d,%d\n",cnt1,cnt2);
    }

    return 0;
}