Answers for "459 - graph connectivity solutions"

459 - graph connectivity solutions

#include<bits/stdc++.h>

using namespace std;
vector<int>adj[1000];
bool visited[1000];
int pre[10000];

void add(int u,int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void dfs(int s)
{
    if(visited[s]) return;

    visited[s]=true;
    for(int i=0;i<adj[s].size();i++)
    {
        int x=adj[s][i];
        if(!visited[x]){
            dfs(x);
        }
    }

}

int main()
{
    int n,m,i,j,t,u,v;
    char c[2],s[5],dumb;

    scanf("%d\n",&t);
    while(t--)
    {
        gets(c);
        n=c[0]-64;
        while(gets(s)){
            if(s[0]=='\0')
                break;
            u=s[0]-65;
            v=s[1]-65;
            add(u,v);
        }
        int cnt=0;
        memset(visited,0,sizeof visited);
        for(i=0;i<n;i++){
            if(!visited[i])
            {
                dfs(i);
                cnt++;
            }
        }
        if(t==0)
        cout<<cnt<<endl;
        else
            cout<<cnt<<endl<<endl;

        for(i=0;i<n;i++)
            adj[i].clear();
    }

}