UVa 459 - Graph Connectivity

// Solution Type: Disjoint Set

/*
Lionel Messi is such a player that you may catch him, you may touch him, you may feel him
and definitely you may Love him.
Lionel Messi is Messi. A little Magician in this World.

*/

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef map<char, int>mpci;

const int mod = 1000007;
const int high = 100;

mpci mp;

int par[30];

void init()
{
    int  i=1;

    for(char c='A' ; c<='Z'; c++ , i++)
    {
        mp[c] = i;
    }
}

void makke_sett(int n)
{
    for(int i=1; i<=n; i++)
    {
        par[i] = i;
    }
}

int findd(int n)
{
    if(par[n] == n) return n;

    else
    {
        return par[n] = findd(par[n]);
    }
}

void unionn(int a , int b)
{
    int u = findd(a);
    int v = findd(b);

    if(u == v) return;
    else par[u] = v;
}

int main()
{
    fast;
    init();
    int t , n;
    string s;
    cin >> t;
    cin.ignore();
    cin.ignore();

    while(t--)
    {
        getline(cin, s);

        n = mp[s[0]];
        //cout << n << "\n";

        makke_sett(n);

        while(getline(cin, s) and s[0])
        {
            //cout << s[0] << " " << s[1] << "\n";

            unionn(mp[s[0]] , mp[s[1]]);
        }

        //cout << "shesh\n";
        int cnt=0;

        for(int i=1; i<=n; i++)
        {
            if(par[i] == i) cnt++;
        }

        cout << cnt << "\n";
        if(t) cout << "\n";
    }

    return 0;
}