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 edges\n";
cin>>n>>m;
cout<<"Enter all the edges\n";
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
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
