#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 :
#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