DFS applications — cycle detection (directed and undirected): Worked examples

Everything here builds on Depth-First Search as the engine. Before any example, we pin down the two algorithms, the adjacency-list input, and the exact vocabulary we'll lean on, so no symbol appears unexplained.

Formula The DIRECTED algorithm (3-colour DFS) — reference for C1–C4, C8–C10

# SETUP: color[] has one slot per vertex, ALL initialised to WHITE
# (size = number of vertices V). GRAY/BLACK are just distinct constants.
color = [WHITE] * V          # every vertex starts unvisited

dfs(u):
    color[u] = GRAY          # entering u: put it on the stack
    for v in adj[u]:         # adj[u] = neighbours reachable in one step
        if color[v] == GRAY:  return True   # back edge -> cycle
        if color[v] == WHITE and dfs(v): return True
    color[u] = BLACK         # leaving u: fully explored, pop
    return False

for u in all vertices:       # OUTER LOOP over every vertex
    if color[u] == WHITE and dfs(u): return True

color[] is an array holding White/Gray/Black for every vertex, all White at the start.
The outer loop restarts DFS from any still-White vertex, so disconnected pieces are all covered (this is what C8 tests).

Definition The vocabulary of the UNDIRECTED method

==visited[]== = a plain boolean array, one slot per vertex, all False initially: visited[u] becomes True once we have entered $u$ at all (there is no Gray/Black — undirected detection does not need finish-timing).
==parent== = the vertex we arrived from. When DFS steps $u \to v$ , we call dfs(v, u), so inside $v$ the value parent equals $u$ . For the very first call there is no parent, written parent = -1.
Why a different method? In an undirected graph every edge $u - v$ is stored both ways in adj[]. That guarantees you will always re-see the edge you just came in on. The Gray/Black machinery answers "is this node still on the stack?" — but here the real question is "did I reach a visited node by a route other than the edge I just used?" A boolean visited[] plus the parent we skip answers that question directly, and cheaply.

Formula The UNDIRECTED algorithm — reference for C5–C7

# SETUP: visited[] has one slot per vertex, ALL initialised to False
# (size = number of vertices V).
visited = [False] * V         # every vertex starts unvisited

dfs(u, parent):
    visited[u] = True                 # entering u
    for v in adj[u]:                  # adj[u] stores each edge BOTH ways
        if not visited[v]:
            if dfs(v, u): return True  # recurse, passing u as the new parent
        elif v != parent:              # visited AND not the edge we came from
            return True                # second route back -> cycle!
    return False

for u in all vertices:                 # OUTER LOOP again, for disconnected graphs
    if not visited[u] and dfs(u, -1): return True

v != parent pardons exactly one thing: the reverse copy of the edge we just crossed.

The scenario matrix

Every cell below is a distinct case class. The examples that follow are each labelled with the cell they cover, so together they tile the whole table.

#	Case class	Directed?	Expected result	Why it's on the list
C1	Simple back edge to an ancestor	Directed	Cycle	The textbook Gray-hit
C2	Cross / forward edge (reaches Black)	Directed	No cycle	The classic false-alarm to avoid
C3	2-node cycle $A \to B \to A$ (smallest directed)	Directed	Cycle	Parent-trick would wrongly miss it
C4	Self-loop $A \to A$ (1-edge cycle)	Directed	Cycle	Degenerate 1-edge input
C5	Triangle $A - B - C - A$	Undirected	Cycle	The genuine second-path-back
C6	Tree (no extra edge)	Undirected	No cycle	Every non-parent test must pass cleanly
C7	Two parallel edges $A - B$ (multigraph)	Undirected	Cycle	`v != parent` alone can fail
C8	Disconnected: cycle hides in component 2	Either	Cycle	The "forgot to loop all components" trap
C9	Real-world: build/task dependencies	Directed	No cycle (DAG)	Word problem → Topological Sort
C10	Exam twist: same edge set, one arrow flipped	Directed	flips No→Yes	Tests true understanding

C1 — Directed back edge to an ancestor

Worked example

$A \to B \to C \to D, D \to B$ Forecast: guess now — is there a cycle, and which node turns out to be Gray at the decisive moment?

dfs(A): A = Gray. Why this step? Entering A puts it on the recursion stack, so it becomes a live breadcrumb; Gray literally means "I am still inside A."
dfs(B): B = Gray. Why? We stepped $A \to B$ and entered B, so B joins the stack. The Gray set is now ${A, B}$ .
dfs(C): C = Gray. Why? Same reason — entering C stacks it. Gray set ${A, B, C}$ .
dfs(D): D = Gray. Why? Entering D stacks it → Gray set ${A, B, C, D}$ . Now we scan D's neighbour $B$ . Why look at $B$ ? We must inspect every outgoing edge; $B$ 's colour decides everything.
color[B] == GRAY → return True. Why this step? $B$ is still on the stack, so edge $D \to B$ climbs back to an ancestor we're still inside = a back edge = cycle.

Figure below: the blue arrows are the tree path $A \to B \to C \to D$ ; the red arrow is the offending edge $D \to B$ , and every yellow node is Gray (on the stack) at the trigger moment. Look at how the red arrow lands on a yellow node — that colour is the whole proof.

Verify: trace the arrows $B \to C \to D \to B$ — that is a closed directed loop of length 3. The Gray set at the trigger was exactly the loop ${B, C, D}$ plus the root $A$ . Consistent. ✅

C2 — Directed cross/forward edge (reaches Black, NO cycle)

Worked example

$A \to B, A \to C, B \to C$ Forecast: DFS will revisit $C$ . Cycle or not?

dfs(A): A = Gray. Why? Entering A stacks it. → follow $A \to B$ .
dfs(B): B = Gray. Why? Entering B stacks it. → follow $B \to C$ .
dfs(C): C = Gray. Why Gray first? Every node is Gray while we're inside it. C has no out-edges, so we finish it: C = Black, pop. Why Black now? All of C's descendants are explored and its call returns, so it leaves the stack.
B = Black, pop. Why? B's loop is done and its call returns → it leaves the stack too.
Back in dfs(A), follow $A \to C$ : color[C] == BLACK. Why does this matter? Black = finished on another branch, not on the current stack. No live loop, so we do nothing.
A = Black. return False. Why? A's loop finished with no Gray hit.

Figure below: the two blue arrows are the tree path $A \to B \to C$ ; the green arrow is $A \to C$ arriving at a node already coloured Black (dark). Notice the green arrow hits a dark node, not a yellow one — that is why it is harmless.

Verify: the only way back to $A$ would need an edge into $A$ ; there is none, so no closed loop is possible. The revisit of $C$ was a forward edge, correctly ignored. ✅

C3 — Smallest directed cycle: 2 nodes

Worked example

$A \to B, B \to A$ Forecast: the naive "ignore the parent" (undirected) trick would skip $B \to A$ as "just where I came from." Watch the 3-colour method instead.

dfs(A): A = Gray. Why? Entering A stacks it. adj[A] = [B] → follow $A \to B$ .
dfs(B): B = Gray. Why? Entering B stacks it. Now scan adj[B] = [A]: color[A] == GRAY.
return True. Why this step? $A$ is on the stack; $B \to A$ is a genuine back edge. A directed graph has no reverse-copy exception (edges are one-way), so we do not skip it — unlike the undirected method.

Figure below: the blue arrow is the tree step $A \to B$ ; the red arrow $B \to A$ lands on a yellow (Gray) node still on the stack. There is no faint "reverse copy" to pardon here — the arrow is a real one-way edge.

Verify: $A \to B \to A$ is a valid directed cycle of length 2. This is exactly Mistake 1 from the parent — the parent-trick would suppress this and give the wrong answer. ✅

C4 — Self-loop (a 1-edge cycle)

Worked example Single node

$A$ with edge $A \to A$ Forecast: does one node with one edge count as a cycle?

dfs(A): A = Gray. Why? Entering A stacks it. Scan adj[A] = [A] → it contains $A$ itself.
color[A] == GRAY (A is currently Gray — it is the node we're inside) → return True.

Figure below: one node with a red self-arrow curling back onto itself. The node is yellow (Gray) at the moment we scan its own edge — so the Gray-check fires immediately.

Verify: a self-loop is a cycle built from a single edge ( $A \to A$ ) — the shortest possible cycle, not a "zero-length" object. In the directed algorithm the Gray-check catches it for free, because a node is Gray during its own scan. (In the undirected algorithm you'd need an explicit v == u self-loop check, since the parent rule alone never anticipates an edge from a node to itself.) ✅

C5 — Undirected triangle (genuine second path back)

Worked example

$A - B, B - C, C - A$ (uses the UNDIRECTED algorithm above) Forecast: every undirected edge is stored both ways. Which visited-node hit is the real cycle and which is the harmless reverse copy?

dfs(A, -1): visited[A]=True. Why set visited now? So any later edge landing on A knows A is already on some path. adj[A] = [B, C]; take $B$ first.
dfs(B, A): visited[B]=True. Why is parent = A? We stepped $A \to B$ , so we passed A as the parent. adj[B] = [A, C]. $A$ is visited but $A ==$ parent → skip. Why skip? $A - B$ is the very edge we just crossed, stored in reverse. Not a cycle.
Next neighbour $C$ : unvisited → dfs(C, B). Why parent = B? We stepped $B \to C$ .
dfs(C, B): visited[C]=True. adj[C] = [B, A]. $B$ is visited and $B ==$ parent → skip (reverse of the edge we came in on).
Next neighbour $A$ : visited and $A \neq =$ parent(=B) → return True. Why this step? $C - A$ reaches $A$ by a different route than the parent chain $A \to B \to C$ . That's a second path = cycle.

Figure below: the blue undirected edges $A - B$ and $B - C$ are the tree path; the red edge $C - A$ is the one that closes the loop. Notice it reaches a node ( $A$ ) that is not C's parent — that mismatch is the cycle signal.

Verify: count edges: 3 nodes, 3 edges. A tree on 3 nodes has $3 - 1 = 2$ edges; the 3rd edge forces exactly one cycle. Matches. ✅

C6 — Undirected tree (no extra edge, NO cycle)

Worked example

$A - B, A - C, C - D$ (a tree, 4 nodes, 3 edges) Forecast: every DFS step will meet its parent as a visited node. Will any of those trip the alarm?

dfs(A,-1): visited[A]=True. Why parent = -1? A is the start; there is no edge we arrived on. adj[A] = [B, C] → go $B$ .
dfs(B,A): visited[B]=True. adj[B] = [A] — only neighbour $A$ = parent → skip → return False. Why safe? The single visited neighbour is exactly the reverse edge.
Back in A → go $C$ : dfs(C,A): visited[C]=True. adj[C] = [A, D]. $A$ =parent, skip. $D$ unvisited → dfs(D,C).
dfs(D,C): visited[D]=True. adj[D] = [C] — only neighbour $C$ = parent → skip → return False.
All returns False → no cycle.

Figure below: the three blue undirected edges branch out with no edge ever closing back — there is no red edge anywhere, which is exactly what "no cycle" looks like. Every visited-hit met is the parent (dashed grey), all pardoned.

Verify: 4 nodes, 3 edges $= n - 1$ , so it must be a tree, which is acyclic by definition. Every visited-node hit was exactly the parent, correctly skipped. ✅ Contrast with C5 where the extra edge broke this.

C7 — Two parallel edges (multigraph) — where `v != parent` can fail

Worked example Two

distinct edges both joining $A$ and $B$ . Call them $e_{1} = A - B$ and $e_{2} = A - B$ . In the adjacency list this means adj[A] = [B, B] and adj[B] = [A, A]. Forecast: intuitively two roads between the same pair of towns is a loop (go out on road $e_{1}$ , come back on road $e_{2}$ ). Does the plain v != parent code catch it? Guess no, and here is a concrete ordering that misses it.

The plain code only remembers the parent node, not which physical edge we used. Watch what happens when B's adjacency list is scanned in the order $[A, A]$ (both copies) before control returns to A:

dfs(A, -1): visited[A]=True. adj[A] = [B, B]. First entry $B$ : unvisited → dfs(B, A).
dfs(B, A): visited[B]=True, parent = A. Scan adj[B] = [A, A]:
- First $A$ : visited, but $A ==$ parent → skip.
- Second $A$ : visited, but $A ==$ parent → skip again. The parent test cannot tell that this second $A$ arrived via the other edge $e_{2}$ , because it only compares node identities, and both entries are the node $A$ .
- B returns False.
Back in dfs(A,-1), second entry $B$ : now visited, and $B \neq = - 1$ (A's parent) → this would fire True.

So in this ordering the outer copy still catches it — but the catch depends entirely on where the second copy sits in the list. If both copies of the $A - B$ edge are consumed inside dfs(B,A) (step 2) and B's recursion returns before A ever inspects its own second $B$ (for instance, if A's list is deduplicated to a single $B$ while B's list keeps both $A$ s), then both visited-hits are judged "== parent" and skipped, and the cycle is reported as absent. Node-based skipping simply has no way to say "I already used one $A - B$ edge; this is a different one."

Fix (parent's Mistake 3): track a visited edge-index, not just the parent node. Give every physical edge a unique id ( $e_{1}, e_{2}$ ); when you traverse an edge, mark that id as used and remember the id you arrived on. Then, when you meet a visited neighbour, skip it only if it is the same edge-id you came in on — a different edge to a visited node is always a cycle. This distinguishes $e_{1}$ from $e_{2}$ even though both connect the same node pair, and also correctly flags a self-loop $u - u$ (a single edge whose two endpoints are the same node) as a cycle.

Figure below: two towns $A$ and $B$ joined by two parallel edges — one blue ( $e_{1}$ , the way out) and one red ( $e_{2}$ , the second way back). The red edge is a different road, so it closes a genuine 2-cycle.

Verify: two parallel edges form a cycle of length 2 in a multigraph (out on $e_{1}$ , back on $e_{2}$ ). Node-based parent skipping cannot distinguish $e_{1}$ from $e_{2}$ , so it is provably insufficient — hence the edge-index fix. ✅

C8 — Disconnected graph, cycle hidden in component 2

Worked example Component 1:

$A \to B$ (no cycle). Component 2: $X \to Y \to Z \to X$ (cycle). Directed. Forecast: if your driver only calls dfs(A), do you ever see $X, Y, Z$ ?

Outer loop hits $A$ (White) → dfs(A): A=Gray→B=Gray→B done→B=Black→A done→A=Black. Returns False.
Outer loop hits $B$ : already Black → skip. Why? Not White, so we don't restart from it.
Outer loop hits $X$ (still White!) → dfs(X): X=Gray→Y=Gray→Z=Gray. Z's edge $Z \to X$ : color[X]==GRAY → return True.

Figure below: two separate clusters. The left cluster ( $A \to B$ , blue) has no loop; the right cluster ( $X \to Y \to Z \to X$ ) closes with a red back edge onto the yellow (Gray) node $X$ . A dashed divider stresses they are disconnected — only the outer loop reaches the right one.

Verify: the cycle $X \to Y \to Z \to X$ is length 3 and lives entirely in a component never touched by the first DFS. Only the outer for u in all vertices: if White: dfs(u) loop reaches it — this is parent's Mistake 4. Drop the outer loop and you falsely report "no cycle." ✅

C9 — Real-world word problem: build/task dependencies

Worked example A build system has tasks.

compile needs codegen; link needs compile; test needs link and codegen. Can we build everything, or is there a deadlock? Forecast: "needs X" means an edge toward the prerequisite. Is this graph acyclic (buildable) or does it loop (deadlock)?

Model as directed edges (task $\to$ its prerequisite): $compile \to codegen, link \to compile, test \to link, test \to codegen .$

dfs(test): test=Gray → link=Gray → compile=Gray → codegen=Gray. codegen has no prereqs → codegen=Black. Why Black? It finished with no Gray hit.
compile=Black, link=Black (each returns in turn). Back in test, edge $test \to codegen$ : codegen is Black → skip (a C2-style forward edge).
test=Black. No cycle → it's a DAG → buildable.

Why DFS here and not, say, Union-Find (DSU)? DSU handles undirected cycle detection; dependencies are directed (order matters), so we need the Gray-stack test. A cycle here would mean two tasks each waiting on the other = deadlock.

Figure below: the four tasks with blue dependency arrows pointing toward prerequisites. The edge $test \to codegen$ is the green forward edge (hits a finished node), and no arrow ever climbs back onto a live node — so it is a clean DAG.

Verify: no cycle ⇔ a valid build order exists via Topological Sort. One valid order (prerequisites first): codegen, compile, link, test. Every edge points backward in this list ⇒ acyclic confirmed. ✅

C10 — Exam twist: flip one arrow, answer flips

Worked example Start with the acyclic chain

$A \to B \to C \to D$ (clearly no cycle). The exam adds an edge. Version (i): add $A \to D$ . Version (ii): add $D \to A$ . Which one creates a cycle? Forecast: same two nodes involved, only the arrow direction differs. Guess which version loops.

Version (i) $A \to D$ :

dfs(A): A=Gray→B=Gray→C=Gray→D=Gray→D done→D=Black; then C,B=Black. Why Black in turn? Each call returns with no Gray hit and pops.
Back in A, edge $A \to D$ : D is Black → forward edge, skip. No cycle. ✅

Version (ii) $D \to A$ :

dfs(A): A=Gray→B=Gray→C=Gray→D=Gray. D's new edge $D \to A$ : color[A]==GRAY → return True. Cycle!

Why the difference? Direction is the whole story in directed graphs. $A \to D$ points to a descendant (already finished, Black) — harmless. $D \to A$ points to an ancestor still on the stack (Gray) — a back edge closing the loop $A \to B \to C \to D \to A$ .

Figure below: the same chain $A \to B \to C \to D$ (blue) twice. On top, the green extra edge $A \to D$ (forward, to a Black node) — no loop. On the bottom, the red extra edge $D \to A$ (back, to the Gray root) — closes a 4-cycle. Same node pair, opposite verdicts.

Verify: Version (ii) has a genuine 4-cycle $A \to B \to C \to D \to A$ . Version (i) has none: node $A$ has in-degree 0, so nothing can ever return to it, ruling out any cycle through $A$ ; and $B, C, D$ form a plain chain. ✅

Recall Self-test: match cell → rule

Which cell shows the parent-trick failing on a directed graph? ::: C3 (the 2-cycle $A \to B \to A$ ). Which cell shows v != parent being insufficient? ::: C7 (parallel/multigraph edges — need edge-index tracking). In C10, why does $A \to D$ give no cycle but $D \to A$ does? ::: $D$ is Black (finished descendant) when $A \to D$ is scanned; $A$ is Gray (live ancestor) when $D \to A$ is scanned. Which cell proves you must keep the outer for every vertex loop? ::: C8 (cycle hidden in a disconnected component). What does visited[] store in the undirected method, and what does parent hold? ::: visited[u] is True once u is entered; parent is the vertex we arrived from (which we skip once).

Connections

Parent topic — cycle detection — the rules these examples exercise.
Depth-First Search — the traversal every example runs on.
Topological Sort — C9's payoff: acyclic ⇔ a build order exists.
Union-Find (DSU) — the undirected alternative (why it doesn't fit C9's directed case).
Back Edges and Edge Classification — Gray-hit = back edge; Black-hit = forward/cross (C1 vs C2).
Strongly Connected Components — cycles are the atoms SCCs are built from.
Bipartite Checking — another DFS-colouring cousin.