459 - Graph Connectivity.cpp

#include<bits/stdc++.h>
using namespace std;
map<char,char>par;

char fin(char a){
    if(par[a]==a) return a;
    return par[a]=fin(par[a]);
}

int main(){

   int t;
    char c;
    char b[10];
    string a;

    cin>>t;
    for(int i=1;i<=t;i++){
        cin>>a;
        cin.get();
        //cin.get();
        c=a[0];
        for(char j='A';j<=c;j++){
            par[j]=j;
        }
        while(1){
            getline( cin, a );
            if( a.size() == 0 ) break;
            char u = fin(a[0]);
            char v = fin(a[1]);
            if(u!=v){
                par[u]=v;
            }


        }
        vector<char>r;
        int flag=0,num=0;
        for(char j='A';j<=c;j++){
            char u = fin(j);
            flag=0;
            for(int k=0;k<r.size();k++){
                if(r[k]==u){
                    flag = 1;
                }
            }
            if(flag ==0){
                num++;
                r.push_back(u);
            }
        }

         /*for(int k=0;k<r.size();k++)
                cout<<r[k]<<" ";
         cout<<"\n";*/
        cout<<num<<"\n";

        if(i<t) cout<<"\n";

    }
	return 0;
}