Find Your Solution Here

UVA

UVA 459 – Graph Connectivity Solution

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

Solution:

#include<bits/stdc++.h>

using namespace std;
bool adj[100][100]={false};
bool visited[100]={false};

void add(int u,int v)
{
    adj[u][v]=true;
    adj[v][u]=true;
}

void dfs(int x)
{
    if(visited[x]) return;
    visited[x]=true;
    for(int i=0;i<100;i++){
        if(adj[x][i] and !visited[i]){
            visited[i];
            dfs(i);
        }
    }


}
void clearVisited()
{
    for(int i=0;i<100;i++){
        visited[i]=false;
    }
}
void clearAdj()
{
    for(int i=0;i<100;i++){
        for(int j=0;j<100;j++){
            adj[i][j]=false;
        }
    }
}

int main()
{
    int n,m,i,j,t,u,v,cnt;
    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);
        }
        cnt=0;
        for(i=0;i<n;i++)
        {
            if(!visited[i]){
                cnt++;
                dfs(i);
            }
        }
        cout<<cnt<<endl;
        if(t) cout<<endl;

        clearAdj();
        clearVisited();

    }

}

Leave a Reply