program to find the connected component in the graph.

Code:-

#include<bits/stdc++.h>
using namespace std;
vector<int> arr[100] ;
int visited[100];

// function definition of finding connected component
void dfs(int n)
{
visited[n]=1;
for(int child: arr[n])
{
if(visited[child]==0)
dfs(child);
}
}

//Driver program
int main()
{
int v,e;
cout<<“Enter number of vertex and edgesn”;
cin>>v>>e;
int a,b;
cout<<“Enter all the edgesn”;
for(int i=0;i<e;i++)
{
cin>>a>>b;
arr[a].push_back(b);
arr[b].push_back(a);
}
int cc_count=0;
//function calling
for(int i=1;i<=v;i++)
if(visited[i]==0)
dfs(i),cc_count++;
cout<<“Connected compponent is : “<<cc_count;
return 0;
}

Output:-

Enter number of vertex and edges
7 7
Enter all the edges
1 5
5 2
5 6
2 8
6 8
6 4
3 7
connected component is : 2



Leave a Reply

Your email address will not be published.