Cycle detection in directed graph
Mon Jan 10 2022 06:54:45 GMT+0000 (Coordinated Universal Time)
Saved by
@vaibhav_55
vector g[100001];
vector visi(100001, 0);
// -->cycle detection for directed graph
bool is_cycle(ll v)
{
visi[v] = 1;
for (ll child : g[v]) {
if (visi[child] == 0) {
if (is_cycle(child) == true)
return true;
}
else {
if (visi[child] == 1)
return true;
}
}
visi[v] = 2;
return false;
}
//here,in visi array we keep the execution state of each node where
//0-> not visited,
//1-> under dfs call
//2-> dfs call completed after visiting all the child's
content_copyCOPY
Comments