Problem Statement

Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.

Problem Link

Detect cycle in a directed graph | Practice | GeeksforGeeks

Reference Link

Detect Cycle in a directed graph using colors - GeeksforGeeks

Algorithm (for DFS + Colors)

Here we consider three different states of vertices

0 : Vertex is not processed yet. Initially, all vertices are WHITE.

1*: Vertex is being processed (DFS for this vertex has started, but not finished which means that all descendants (in DFS tree) of this vertex are not processed yet (or this vertex is in the function call stack)*

2 : Vertex and all its descendants are processed. While doing DFS, if an edge is encountered from current vertex to a GRAY vertex, then this edge is back edge and hence there is a cycle.

Steps:

1. Call DFS on each node of graph G, if it returns true then there exists a cycle.
2. Inside the DFS function if the vertex is already inside a recursion call stack then cycle exists and return true.
3. If the vertex u is unvisited then change its state to 1 and recursively call DFS on its descendants, if DFS returns true then there exists a cycle.
4. After all the descendants of vertex u have been processed change its state to 2.

Code (Using DFS + Colors)

class Solution
{
    public:
	//Function to detect cycle in a directed graph.
	bool isCyclic(int V, vector<int> adj[]) 
	{
	   	vector<int> visited(V,0);
	   	
	   	for(int u=0;u<V;u++)
	   	{
	   	    if(dfs(u,adj,visited))
	   	    return true;
	   	    
	   	}
	   	return false;
	}
	
	bool dfs(int u,vector<int> adj[],vector<int> &visited)
	{
	    if(visited[u]==1)
	    return true;
	    
	    **if(visited[u]==0)** // if u is unvisited yet, **not writing this if statement may result to TLE**
	    {
	        visited[u] = 1; // make u inside recursion call stack
	    
	        for(int v:adj[u])
	        {
	        
	        if(dfs(v,adj,visited))
	        return true;
	        }
	    
	        visited[u] = 2; // u and all its descendants have been visited
	    }
	   
	    return false;
	}
};

Code (Using the concept of back edge and recursion call stack)