Sunday 31 July 2016

Find connected components using DFS

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> a[1000];
int  e,v,vis[1000];

void dfs(int n)
{
vis[n]=1;
for(int i=0;i<a[n].size();i++)
{
if(vis[a[n][i]]==0)
dfs(a[n][i]);
}
}

int main() {

int i,j,k,x,y;
// number of vertices and edges
cin>>v>>e;

for(i=0;i<e;i++)
{
//input all edges of graph
cin>>x>>y;
//for undirected graph
a[x].push_back(y);
a[y].push_back(x);    
}

for(i=0;i<v;i++)
vis[i]=0; //Initially mark all vertices unvisited
k=0;  //keep count of connected components
for(i=0;i<v;i++)
{
if(vis[i]==0){
dfs(i);
k++;
}

}

cout<<"Number of  Connected components in graph = "<<k;
// your code goes here
return 0;
}





Input :
6
4
1 2
2 3
1 3
4 5

Output :
Number of Connected components in graph = 3

No comments:

Post a Comment