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**

**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

## 0 Comments