The easiest DFS (depth first search) Problem: UVa 459

N:B First understand the core dfs algorithm and implement it in your own way.There are a lot of resources in online like GeeksForGeeks and in Wiki.


Problem Link: Graph Connectivity
For more practice : Go to here

Source code in C++:

#include<bits/stdc++.h>
#define lli long long int
#define file freopen("in.txt","rt",stdin)
using namespace std;
vector<int> node[101];
int vis[101];
void dfs(int n)
{
    for(int i=0; i<node[n].size(); i++)
    {
        if(vis[node[n][i]]==0)
        {
            vis[node[n][i]] = 1;
            dfs(node[n][i]);
        }
    }
}


int main()
{
    char str[3];
    int test,temp,sum=0;
    char f,s;
    cin>>test;
    scanf("\n");
    while(test--)
    {
        gets(str);
        sum=0;
        temp = str[0];
        memset(vis,0,sizeof vis);
        while(gets(str) and str[0])
        {

            node[str[0]].push_back(str[1]);
            node[str[1]].push_back(str[0]);
        }

        for(int i=65; i<=temp; i++)
        {
            if(vis[i]==0)
            {
                sum++;
                dfs(i);
            }
        }
        cout<<sum;
       if(test)
       {
           cout<<"\n\n";
       }
       else
        cout<<"\n";
       for(int i=65;i<=90;i++)
        node[i].clear();
    }
    return 0;
}