UVa problem 459 - Graph Connectivity

problem link:

Discuss: you can solve this problem in many ways like dfs,bfs, disjoint set. i used here disjoint set.just simply put the array element in vector and then erase every duplicate element for in similar set only number exist in vector. the i just count the number of element in the vector. there is also a case where no connectivity among nodes. if use scanf for scan newline than on that case it will not give you any output. so where any problem if need to scan a line only than use getchar() instead of scanf. and there is no more tricky part in this problem.


try your self, before see the code




#include<bits/stdc++.h>
using namespace std;
int ara[100000],n;
int fnd(int u)
{
    if(ara[u]==u)
        return u;
    else
        return ara[u]=fnd(ara[u]);
}
int makeUnion(int a,int b)
{
    int x=fnd(a);
    int y=fnd(b);
    if(x!=y)
    {
        for(int i=1;i<=n;i++)
        {
            if(ara[i]==y)
                ara[i]=x;
        }
        //ara[x]=y;
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
    int t;
    cin >>t;
    while(t--)
    {
        int a,b;
        char c;
        int i,j,cnt=0,flag=0;
        string str;
        vector<int>vec;
        cin >>c;
        n=c-64;
        for(i=1;i<=n;i++)
            ara[i]=i;
           getchar();
        while(1)
        {
            getline(cin,str);
            if(str.length()==0)
                break;
            a=str[0]-64;
            b=str[1]-64;

            makeUnion(a,b);

        }
        for(i=1;i<=n;i++)
        {
            vec.push_back(ara[i]);
            //cout <<ara[i]<<' ';

        }
        sort(vec.begin(),vec.end());
        vec.erase(unique(vec.begin(),vec.end()),vec.end());
        cout <<vec.size()<<endl;
        if(t>0)
        cout <<endl;
        vec.clear();
    }
    return 0;

}