program to find the cycle in the graph .

If a graph does not have the cycle then it’s all vertex have only one parent. 

and if have cycle then atleast one vertex have more than one parent.

 Code:-

#include<bits/stdc++.h>
using namespace std;
vector<int> arr[100];
int visited[100];
bool dfs(int v,int p)
{
visited[v]=1;
for(int child:arr[v])
{
if(visited[child]==0)
{
auto t=dfs(child,v);
if(t==true)
return true;
}
else
if(child!=p)
return true;
}
return false;
}
int main()
{
int n,m;
cout<<“Entet the number of vertex and number of edgesn”;
cin>>n>>m;
cout<<“Enter all the edgesn”;
int a,b;
for(int i=0;i<m;i++)
{
cin>>a>>b;
arr[a].push_back(b);
arr[b].push_back(a);
}
auto ans=dfs(1,0);
if(ans==true)
cout<<“Graph have cycle”;
else
cout<<“Graph does not have cycle”;
return 0;
}


Output:-

for the graph


As we can see it have cycle .So let’s check by the code

Enter the number of vertex and number of edges
5 5
Enter all the edges
1 2
2 3
2 4
3 4
4 5

Graph have cycle



Leave a Reply

Your email address will not be published.