UVA-459 - Graph Connectivity- ( Category : DFS )

Problem link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=400

Solution :

#include<bits/stdc++.h>

using namespace std;

map<char,int>mp;
bool visited[30];
vector<int>v[100];

void DFS(int n)
{
    visited[n]=true;
    int u;

    for(int i=0; i<v[n].size(); i++)
    {
        u=v[n][i];
        if(!visited[u])
        {
            DFS(u);
        }
    }
}
int main()
{

//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);

    int t;
    int ok=0;
    scanf("%d",&t);
    getchar();


    while(t--)
    {

        if (ok>0) cout<<endl;
        ok++;
        //getchar();

        int cnt=0,i,j,k,l=1,node;

        char w,x,y;
        string s;
        cin>>w;
        getchar();
        node=w-64;

        while(getline(cin,s))
        {

            x=s[0];
            if (x==NULL) break;
            y=s[1];
            //getchar();
            if(mp.find(x)==mp.end())
            {
                mp[x]=l;
                l++;
            }
            if(mp.find(y)==mp.end())
            {
                mp[y]=l;
                l++;
            }
            v[mp[x]].push_back(mp[y]);
            v[mp[y]].push_back(mp[x]);


        }
        memset(visited,0,sizeof(visited));
        for(i=1; i<=node; i++)
        {


            if(!visited[i])
            {
                DFS(i);
                cnt++;
            }
        }

        cout<<cnt<<endl;
        mp.clear();

        for(i=0; i<100; i++) v[i].clear();
    }


}