that_wasnt_me's blog

I saw this code somewhere. Can someone please explain this code for cycle detection in directed graph ?
By that_wasnt_me, history, 6 years ago, In English 
bool findLoop(int v) 
{
	if(vis[v]==1)
		return 1;
	if(vis[v]==2)
		return 0;
	vis[v]=1;
	for(auto &it:g[v])
	{
		if(findLoop(it))
			return 1;
	}
	vis[v]=2;
	return 0;
}

bool checkLoop()
{
	fill(vis+1, vis+n+1, 0);
	for(int i=1;i<=n;i++)
	{
		if(!vis[i] && findLoop(i))
			return 1;
	}
	return 0;
}
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This algorithm "colours" nodes in 3 "colours": 0, 1 and 2. Zero represents a completely unprocessed node, one represents a node that is in processing, msaning that we are currently visiting nodes that were reached from it in our DFS traversal; and black represents a node that we have got out of. Now, a cycle only exists if you can reach a node from itself. If you reach an already processed (black) node, that is not going to be a cycle, since you visited it from somewhere else in the graph. See this link https://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/amp/

→ Reply