Friday, April 24, 2015

UVa - 459 - Graph Connectivity

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int par[33];
int cnt;

int find_set(int r){
if(par[r] == r)return r;
return par[r] = find_set(par[r]);
}

void merge_set(int x, int y){
int u = find_set(x);
int v = find_set(y);
if(u != v)par[u] = v, cnt--;
}

int main(){
    int t, m, n, blank = 0;
    char s;
    string node;
    cin >> t;
    while(t--){
        if(blank)cout << endl;
        cin >> s;
        cnt = s-64;
        for(int i = 1; i <= s-64; i++)par[i] = i;///create set
        cin.ignore();
        while(getline(cin, node)){
            if(node == "")break;
            m = node[0]-64;
            n = node[1]-64;
            merge_set(m, n);
        }
        cout << cnt << endl;
        blank = 1;
    }
    return 0;
}

No comments:

Post a Comment