Detect Cycle in an directed graph - DFS

Practice Link

Given an directed graph with V vertices and E edges, check whether it contains any cycle or not.

No Cycle

Cycle exists

Note#

Graph can also be disconnected -> Check for every node as source/starting node.

Cannot just use visited node as a check for cycle. Following case shows that 2 is visited and not the parent for 3, but still cycle not there.

DFS#

In a directed graph, the simple "visited neighbor that isn't my parent" trick from undirected graphs no longer works — a visited node might have been reached via a completely different path and not form a cycle with the current one. The correct signal is a back-edge: an edge from a node back to an ancestor in the current DFS recursion path. We detect this by maintaining a separate recursion stack (recStk) that tracks only the nodes on the active DFS path; the global visited array tracks all nodes ever explored.

• A cycle exists only if there is a back-edge — a node that points to one of its ancestors in the DFS tree.
• Maintain a visited array (all ever-explored nodes) and a recStk array (nodes in the current recursion stack / active DFS path).
• When visiting a neighbor: if it is unvisited, recurse into it; if it is already in recStk, a back-edge is found → cycle exists.
• While backtracking, remove the node from recStk so sibling paths are not falsely flagged.

Tip: After DFS terminates, the nodes remaining in recStk mark the cycle — useful for printing the cycle's members.

Implementation#

bool isCyclicDFS(vector<vector<int>> adj, vector<bool> &visited, vector<bool> &recStk, int u)
{
    visited[u] = true;
    recStk[u] = true;
    
    for(int v: adj[u])
    {
        if(!visited[v] && isCyclicDFS(adj, visited, recStk, v))
            return true;
        else if(recStk[v])
            return true;
    }
    
    recStk[u]=false;
    return false;
}
// Function to detect cycle in a directed graph.
bool isCyclic(int V, vector<vector<int>> adj) {
    vector<bool> visited(V, false);
    vector<bool> recStk(V, false);
    
    for(int i=0;i<V;i++)
    {
        if(!visited[i] && isCyclicDFS(adj, visited, recStk, i))
            return true;
    }
    return false;
}

Complexities#

Time Complexity: O(V+E) + O(N)#

We are exploring every vertex V and exploring all its edges. O(N) -> For covering disconnected components

Same TC as DFS

Space Complexity: O(N)+O(V+E),#

O(N) to keep visited nodes, and O(V+E) to create the adjacency list.