Cycle Detection in Directed Graph
#include <bits/stdc++.h>
using namespace std;
class Graph
{
list<int> *l;
int v;
public:
Graph(int v)
{
this->v = v+1;
l = new list<int>[v+1];
}
void addEdge(int x, int y)
{
l[x].push_back(y);
// l[y].push_back(x);
}
bool dfs(int node, vector<bool> &visited, vector<bool>&stack)
{
visited[node] = true;
stack[node]=true;
for (auto nbr : l[node])
{
if (!visited[nbr] && !stack[nbr])
{
bool foundCycle = dfs(nbr, visited, stack);
if (foundCycle)
return true;
}
else if (stack[nbr] && visited[nbr])
return true;
}
stack[node]=false;
return false;
}
bool constainCycle()
{
vector<bool> visited(v, false);
vector<bool>stack(v,false);
for(int i=0; i<v; i++){
if(!visited[i]){
if(dfs(i,visited,stack))return true;
}
}
return false;
}
};
int main()
{
Graph g(5);
g.addEdge(0,1);
g.addEdge(1,2);
g.addEdge(2,3);
g.addEdge(0,4);
g.addEdge(4,5);
g.addEdge(0,5);
cout<<g.constainCycle();
return 0;
}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.