topic: DSU

UVA-459.cpp

#include <iostream>
using namespace std;
int link[5009], size[5009];
void init(int c)
{
    for(int i = 0; i < c; i++) link[i] = i, size[i] = 1;
}

int root(int x)
{
    while(x != link[x]) x = link[x];
    return x;
}

bool same(int a, int b)
{
    return root(a) == root(b);
}

void unite(int a, int b)
{
    a = root(a);
    b = root(b);
    if(a < b) swap(a, b);
    size[a] += size[b];
    link[b] = a;
}
 
 
int main(){
    int T,n,x,y,ans;
    char c;
    string s;
    
    scanf("%d\n\n",&T);
    
    for(int tc=1;tc<=T;tc++){
        getline(cin,s);
        n=s[0]-'A'+1;
        
        ans=n;
        init(ans);
        
        while(1){
            if(!getline(cin,s) || s.empty()) break;
            
            x=s[0]-'A'; y=s[1]-'A';
            
            if(!same(x, y)){
                unite(x,y);
                ans--;
            }
        }
        
        if(tc!=1) printf("\n");
        printf("%d\n",ans);
    }
    
    return 0;
}