DSA sheet · Graphs · Cycle detection pattern (directed, DFS)

Detect a Cycle in a Directed Graph (DFS)

Same question as Problem 11, but now every edge is a one-way street. The teacher first shows that the undirected method (visited + parent) gives the wrong answer here, and why. Then she fixes it with a second array, path visited, that remembers which nodes are on the path we are walking right now. Finally she squeezes both arrays into one array with three values: 0 = never seen, 1 = on my current path, 2 = finished. This three-colour DFS is the same tool used later for Course Schedule and Eventual Safe States.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Why the undirected method fails here (two counter-examples)
• Part B · DFS with visited + path visited
• Part C · One array with 0 / 1 / 2 (the teacher's final code)
• Part D · The same with an explicit stack (no recursion limit)
• Part E · Revision page

Part 0 · Before starting

Graph words used on this page

• Node (vertex) and edge; V = number of nodes (0 … V−1), E = number of edges.
• Directed edge (u)→(v): you may go from u to v, but not back from v to u (unless there is a separate edge v→u). Undirected edge (u)—(v): both ways. Weighted: a cost on the edge; not used here.
• Directed cycle: start at a node, follow arrows in their direction, and get back to the start. A shape that "looks like a loop" on paper is not a cycle if one arrow points the wrong way.
• Out-degree of u: how many arrows leave u. All out-degrees add up to exactly E, because each edge leaves from exactly one node.

  looks like a loop, but is NOT a cycle      a real directed cycle
        (0)                                         (0)
       ↙   ↘                                       ↙   ↖
    (1) ———→ (2) ———→ (3)                       (1) ———→ (2) ———→ (3)
  0→1→2 and 0→2: no arrow back to 0            0→1→2→0

Building the adjacency list (one way only)

The input is an edge list. Unlike Problem 11, we add each edge once, from u to v. Adding v→u too would invent roads that don't exist.

V = 4
edges = [[0, 1], [0, 2], [1, 2], [2, 3]]

graph = [[] for _ in range(V)]
for u, v in edges:
    graph[u].append(v)        # only u → v

print(graph)   # [[1, 2], [2], [3], []]

Other input forms you may see: an adjacency matrix (V×V of 0/1, too big for large V) or the adjacency list already given. Here we always build the list.

Visited, components, and DFS (recap)

• visited: one mark per node, so we never explore a node twice and never spin forever.
• Components: the graph may be in several pieces. As in Problem 11, an outer loop starts a DFS from every node that is still unvisited. Her example: nodes 0–3 have no cycle, but a second piece starting at 4 does. Starting only at 0 would miss it.
• In a directed graph the outer loop matters even inside one piece: with an edge 1→0, a DFS from 0 cannot reach 1. The loop later starts at 1 anyway.
• DFS with recursion: mark the node, call DFS on each unvisited neighbour, come back when it's done. The call stack at any moment holds the exact path from the start node to where we are. That "current path" is the key idea of this page.

Part A · Why the undirected method fails here

GFG: "Directed Graph Cycle"

1The question in simple words

You get V and a list of directed edges [u, v] meaning u → v. Return True if you can follow arrows from some node and come back to it, else False. The graph may have several components. Constraints are like Problem 11 (V, E up to about 10⁵), so we again need O(V + E); anything quadratic would be around 10¹⁰ steps and TLE.

2Counter-example 1: the parent rule says "cycle" when there is none

The teacher's graph: edges 0→1, 0→2, 1→2, 2→3. Run the Problem 11 rule ("visited neighbour that is not my parent → cycle"):

        (0)                    dfs(0, parent −1): mark 0, go to 1
       ↙   ↘                   dfs(1, parent 0):  mark 1, go to 2
    (1) ———→ (2) ———→ (3)      dfs(2, parent 1):  mark 2, go to 3
                               dfs(3, parent 2):  mark 3, no arrows out. Back up …
                        back in dfs(0): next neighbour is 2
                          2 is visited, and 0's parent is −1, 2 ≠ −1
                          → "cycle" ✗ WRONG

From 2 you can only go to 3. There is no arrow back to 0. Node 2 was visited because of an earlier, finished branch (0 → 1 → 2), not because we are walking around a loop. Two arrows meeting at the same node (like 0→2 and 1→2) is not a cycle in a directed graph.

3Counter-example 2: the parent rule says "no cycle" when there is one

My own addition, to show the parent rule isn't only too strict but can also be too lenient.

  (0) ⇄ (1)        edges 0→1 and 1→0: a cycle of length 2

  dfs(0, parent −1): mark 0, go to 1
  dfs(1, parent 0):  neighbour 0 is visited, but 0 IS my parent → "ignore"
  → finishes with "no cycle" ✗ WRONG

In an undirected graph, skipping the parent is correct because "1 to 0" is the same edge we came along. In a directed graph, 1→0 is a different edge from 0→1, so going back to 0 is a real loop. The parent check would hide it.

Part B · DFS with visited + path visited

1The idea in simple words

Keep two arrays of size V:

• visited[x]: "x has ever been reached". Once 1, it stays 1 forever.
• path_vis[x]: "x is on the path I'm walking right now". Set to 1 when DFS enters x, and set back to 0 when DFS leaves x (returns from it).

2What the constraints tell us

• V, E up to 10⁵ → one DFS over everything, O(V + E). Two arrays of size V are only O(V) extra memory, fine.
• Recursion may go V deep → in Python raise the recursion limit (or use Part D).

3Intuition: a trail of breadcrumbs you pick up on the way back

Think of exploring a one-way road network. You put a permanent flag on every town you have ever visited. You also drop a breadcrumb in each town on your way forward, and pick it up when you turn back. The breadcrumbs always show exactly the route from your starting town to where you stand.

• If a road leads to a town with a breadcrumb, that town is behind you on your own route, and this road takes you back to it. You are going round in a loop → cycle.
• If a road leads to a town with a flag but no breadcrumb, you explored it fully in an earlier trip and came back from it. It's a dead end for loops → ignore.

4Building the logic from her example

The three situations for a neighbour

The teacher points out that the third case needs no code: we neither return True nor make a call, so we just let the loop move to the next neighbour.

Re-running her example with path visited

Edges 0→1, 0→2, 1→2, 2→3. Go 0 → 1 → 2 → 3, marking visited = 1 and path_vis = 1 on each. Node 3 has no arrows out, so we return. On the way back, each node clears its own breadcrumb:

  node:        0  1  2  3
  going down   visited   1  1  1  1
               path_vis  1  1  1  1      (path is 0 → 1 → 2 → 3)
  back at 0    visited   1  1  1  1
               path_vis  1  0  0  0      (3, 2, 1 have returned)

Now 0 looks at its second neighbour, 2: visited = 1 but path_vis = 0. Node 2 is not on my path, so this is the harmless third case → no cycle. ✓ The false alarm of Part A is gone.

Why unmark only path_vis and not visited too?

  (0)→(1)→(3)→(4)→(6)→ …
    ↘    ↗   ↘    ↗
     (2)       (5)          k diamonds → 2ᵏ routes from 0 to the end

5Approach steps

1. Build the adjacency list one way (u → v).
2. Make visited and path_vis, both all 0.
3. For each node i that is not visited: if dfs(i) is True → return True.
4. In dfs(node): set visited[node] = 1 and path_vis[node] = 1.
5. For each neighbour: not visited → recurse, pass True up. Visited and on path → return True. Otherwise skip.
6. After the loop: path_vis[node] = 0 (leaving the path), return False.
7. After the outer loop: return False.

6Code (Python)

import sys
sys.setrecursionlimit(10**6)

class Solution:
    def isCyclic(self, V, edges):
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)              # one way only

        visited = [0] * V
        path_vis = [0] * V
        for i in range(V):                  # every component
            if visited[i] == 0:
                if self.dfs(i, graph, visited, path_vis):
                    return True
        return False

    def dfs(self, node, graph, visited, path_vis):
        visited[node] = 1
        path_vis[node] = 1                  # node joins the current path
        for nb in graph[node]:
            if visited[nb] == 0:
                if self.dfs(nb, graph, visited, path_vis):
                    return True
            elif path_vis[nb] == 1:         # arrow back into my own path
                return True
        path_vis[node] = 0                  # leaving: off the path, but still visited
        return False

7Code line by line

8Dry run

Her second graph: flip the arrow between 0 and 2 so it points 2 → 0. Edges 0→1, 1→2, 2→0, 2→3 → graph: 0:[1] · 1:[2] · 2:[0,3] · 3:[].

        (0)
       ↙   ↖
    (1) ———→ (2) ———→ (3)       0 → 1 → 2 → 0 is a real cycle

The 4 digits are nodes 0, 1, 2, 3. Node 3 is never visited: we stop at the first cycle.

Notice: the nodes with path_vis = 1 are exactly the calls on the stack. path_vis is just a quick way to ask "is this node on the stack?" in O(1).

9Complexity & remember

• Time O(V + E). One DFS call per node (V). The for loops together run once per arrow. Her count on the example: node 0 loops 2 times, node 1 once, node 2 once, node 3 zero times → 4 = E in total, not 4 per node. Compare the undirected version: there each edge sits in two lists, so it was V + 2E. Here each edge is stored once, so it's V + E.
• Space O(V + E) for the adjacency list (V lists, E entries in total), plus O(V) for visited, O(V) for path_vis, O(V) for the call stack. V + E is the biggest part, so the two O(V) arrays don't change the big-O. They are still extra memory, which Part C removes.

Part C · One array with 0 / 1 / 2

1What changes from Part B

Look at the pairs (visited, path_vis) a node can have: (0,0) never seen, (1,1) on the path, (1,0) finished. Only three combinations ever happen. So one number per node is enough:

The teacher's trick: we can't set visited back to 0 when returning (that would cause repeated work, see Part B). But we can change the 1 into a 2. The value then says both "seen" (not 0) and "not on my path any more" (not 1).

2The rules with one array

• Enter a node → set it to 1.
• Neighbour is 0 → recurse.
• Neighbour is 1 → it's on my path → cycle.
• Neighbour is 2 → finished earlier → do nothing (again no code needed).
• Leave a node → set it to 2, return False.

Only two lines change from Part B: path_vis[node] = 0 becomes state[node] = 2, and the check "visited and path_vis == 1" becomes just state[nb] == 1.

3Code (Python)

import sys
sys.setrecursionlimit(10**6)

class Solution:
    def isCyclic(self, V, edges):
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)

        state = [0] * V                 # 0 new, 1 on path, 2 finished
        for i in range(V):
            if state[i] == 0:
                if self.dfs(i, graph, state):
                    return True
        return False

    def dfs(self, node, graph, state):
        state[node] = 1                 # entering: on the current path
        for nb in graph[node]:
            if state[nb] == 0:
                if self.dfs(nb, graph, state):
                    return True
            elif state[nb] == 1:        # back into my own path
                return True
            # state 2: finished earlier, ignore
        state[node] = 2                 # leaving: finished
        return False

4Code line by line (only the new parts)

5Dry run: no cycle (the Part A graph)

Edges 0→1, 0→2, 1→2, 2→3 → graph 0:[1,2] · 1:[2] · 2:[3] · 3:[]. The state column lists nodes 0, 1, 2, 3.

  snapshot at step 8   (1 = on path, 2 = finished)
          [0:1]
         ↙     ↘
    [1:2] ———→ [2:2] ———→ [3:2]
  0's arrow to 2 hits a finished node → not a cycle

With the cycle graph (2→0 instead of 0→2), the run is the same as Part B's dry run: at dfs(2), node 0 has state 1 → True.

6Complexity & remember

• Time O(V + E), the same as Part B.
• Space O(V + E): the adjacency list, one O(V) array instead of two, and the O(V) call stack. On paper the big-O is the same; in practice it saves one array of size V.

Part D · The same with an explicit stack

Not from the video. For a chain of 10⁵ nodes, the recursive version goes 10⁵ calls deep. Here the "current path" is our own list. Each entry is (node, index of the next neighbour to look at), so a node can pause and continue its neighbour loop exactly like a paused recursive call.

• Same: states 0 / 1 / 2 and the three rules.
• Changes: "call dfs(nb)" becomes "set nb to 1 and push it". "return from node" becomes "set node to 2 and pop it".

class Solution:
    def isCyclic(self, V, edges):
        graph = [[] for _ in range(V)]
        for u, v in edges:
            graph[u].append(v)

        state = [0] * V
        for start in range(V):
            if state[start] != 0:
                continue
            state[start] = 1
            stack = [(start, 0)]               # (node, next neighbour index)
            while stack:
                node, i = stack[-1]
                if i < len(graph[node]):
                    stack[-1] = (node, i + 1)  # next time, look at the next one
                    nb = graph[node][i]
                    if state[nb] == 0:
                        state[nb] = 1          # "call" nb
                        stack.append((nb, 0))
                    elif state[nb] == 1:
                        return True
                else:
                    state[node] = 2            # "return" from node
                    stack.pop()
        return False

The nodes in stack are exactly the nodes with state 1, the current path. Time and space O(V + E), with no recursion limit.

Part E · Revision page

s = Solution()
print(s.isCyclic(4, [[0, 1], [0, 2], [1, 2], [2, 3]]))        # False
print(s.isCyclic(4, [[0, 1], [1, 2], [2, 0], [2, 3]]))        # True
print(s.isCyclic(2, [[0, 1], [1, 0]]))                        # True
print(s.isCyclic(6, [[0, 1], [1, 2], [3, 4], [4, 5], [5, 3]]))  # True
print(s.isCyclic(3, []))                                      # False

Based on this video: Detect Cycle in a Directed Graph using DFS