DFS applications — cycle detection (directed and undirected)

WHY two different rules?

WHY colors matter (directed): In a directed graph, reaching a black node again is fine — it just means two paths merge (a cross/forward edge), no cycle. But reaching a gray node means you found a path that loops back to an ancestor you're still inside → cycle.

WHY parent-exception (undirected): Each undirected edge $u-v$ is stored both ways. When you go $u \to v$ , then from $v$ you'll see the edge back to $u$ which is already visited. That is NOT a cycle — it's the same edge. So you must ignore the immediate parent. But seeing any other already-visited node means a genuine second path back → cycle.

Figure — DFS applications — cycle detection (directed and undirected)

HOW: Directed cycle detection (3-color DFS)

Formula Directed algorithm (derived from states)

Maintain color[] all White. For each White node, run dfs.

dfs(u):
    color[u] = GRAY
    for v in adj[u]:
        if color[v] == GRAY:   return True   # back edge → cycle
        if color[v] == WHITE and dfs(v): return True
    color[u] = BLACK
    return False

Why GRAY check first? A neighbor that is gray sits on the current stack → an edge to it closes a loop. Why allow BLACK? Black means finished on another branch — no live loop.

HOW: Undirected cycle detection

Formula Undirected algorithm (derived)

Maintain visited[]. Run dfs(u, parent):

dfs(u, parent):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            if dfs(v, u): return True
        elif v != parent:        # visited AND not the edge we came from
            return True          # cycle!
    return False

Why v != parent? The reverse copy of the edge $parent-u$ will be seen; ignoring it prevents a false alarm. Any other visited neighbor = a second route = real cycle.

Common mistake Steel-manning the classic errors

Mistake 1 — using parent-trick on directed graphs. It feels right ("ignore where I came from"). Why it fails: directed edges aren't symmetric; there's no spurious reverse edge to ignore, and a true 2-cycle $A\to B\to A$ would be wrongly skipped. Fix: use 3 colors, check GRAY.

Mistake 2 — using GRAY/colors logic on undirected & forgetting parent. You'd flag the immediate-parent reverse edge as a cycle on EVERY edge. Why tempting: "visited node reached = cycle" sounds universal. Fix: add v != parent.

Mistake 3 — parallel edges / self-loops in undirected. With two edges between $u,v$ , the v != parent test can miss the cycle. Fix: track edge-index visited, not just parent, when multigraphs are allowed. A self-loop $u-u$ is itself a cycle.

Mistake 4 — not iterating over ALL components. A cycle may hide in a disconnected component. Fix: loop for u: if not visited[u]: dfs(u).

Recall Feynman: explain to a 12-year-old

Imagine walking through a maze while unrolling a string behind you. Directed maze (one-way doors): if a door leads you to a spot where your string is still lying on the floor in front of you (you haven't packed it up yet), you've gone in a circle. If the string there is already rolled back up (you finished that area), it's fine. Undirected maze (normal doors): every door you walk through, the door behind you is the one you just came from — ignore it! But if you reach a room you've already been in through a different door, the maze has a loop.

Complexity

Flashcards

Directed graph: a cycle exists iff DFS finds what kind of edge?

A back edge — an edge to a node currently GRAY (on the recursion stack).

What do the three DFS colors WHITE/GRAY/BLACK mean?

White = unvisited; Gray = visited but still on the recursion stack; Black = fully finished/popped.

Why doesn't reaching a BLACK node in a directed graph indicate a cycle?

Black means that node's DFS already finished on another branch; the edge is a cross/forward edge, not a loop back onto the live stack.

Undirected cycle detection: condition for a cycle during DFS?

An edge to an already-visited node that is NOT the immediate parent.

Why the v != parent check in undirected DFS?

Each undirected edge is stored both directions; the reverse copy of the edge we came from would falsely look like a cycle, so we exclude the parent.

Why can't you use the parent-trick for directed graphs?

Directed edges aren't symmetric, so there's no spurious reverse edge; using parent-trick would also miss a true 2-cycle A→B→A.

Time complexity of DFS cycle detection?

O(V + E), space O(V).

A tree on n nodes has how many edges, and what does an extra edge cause?

n−1 edges; any additional edge creates exactly one cycle.

How do you ensure you detect cycles in disconnected graphs?

Loop over all vertices and start a DFS from any unvisited one.

Smallest directed cycle and smallest undirected cycle (simple)?

Directed: 2 nodes (A→B→A) or self-loop; Undirected (simple): 3 nodes (triangle).

Connections

Depth-First Search — the traversal engine these rely on.
Topological Sort — only possible iff the directed graph is acyclic (DAG); same back-edge test.
Union-Find (DSU) — alternative undirected cycle detection without DFS.
Back Edges and Edge Classification — tree/back/forward/cross edges.
Strongly Connected Components — built on DFS finish times.
Bipartite Checking — another DFS/BFS coloring application.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, cycle detection ka idea simple hai: DFS se hum graph mein "deep" jaate hain, aur agar chalte-chalte hum kisi aise node pe wapas pahunch jaayein jisko abhi explore kar hi rahe the, toh matlab loop ban gaya. Bas directed aur undirected mein "rule" thoda alag hota hai.

Directed graph mein hum teen colors use karte hain — WHITE (abhi tak nahi gaye), GRAY (gaye hain par abhi recursion stack pe hai), aur BLACK (poora khatam). Agar DFS ke dauraan koi edge GRAY node ki taraf jaaye, toh wo back edge hai aur cycle confirm. BLACK node milna theek hai — wo doosri branch pe finish ho chuka, koi loop nahi.

Undirected graph mein har edge dono taraf store hoti hai, isliye jis node se aaye ho (parent) usko wapas dekhna normal hai — usko ignore karo. Lekin agar koi doosra already-visited node mil jaaye (jo parent nahi hai), toh samajh lo cycle hai, kyunki ek hi node tak do raste ban gaye. Yaad rakhne ka trick: "GRAY means cycle (directed), Parent pardon karo aur baaki visited node pe panic karo (undirected)." Dono ka time complexity $O(V+E)$ hai, aur disconnected graph ke liye har component se DFS chalana mat bhoolna.

DFS applications — cycle detection (directed and undirected)

WHY two different rules?

HOW: Directed cycle detection (3-color DFS)

HOW: Undirected cycle detection

Complexity

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections