Cycles and topological order
Detect a cycle with a parent check when undirected and three colours when directed, then peel a dependency graph into a valid order and prove one exists.
Cycle detection looks like one problem and is two. In an undirected graph every edge is stored twice, so the naive check reports a cycle on the first edge it walks. In a directed graph a node can be reached twice with no cycle in sight. The two need different bookkeeping, and getting that wrong is the standard way to fail this topic.
Undirected: skip the edge you came in on
Building the graph the usual way puts v in graph[u] and u in graph[v]. A DFS
that steps u → v then immediately sees v → u and calls it a cycle. It is not one
— it is the same edge, read backwards. Pass the parent down and ignore it:
def has_cycle(graph, n):
seen = [False] * n
for s in range(n):
if seen[s]:
continue
stack = [(s, -1)]
seen[s] = True
while stack:
u, parent = stack.pop()
for v in graph[u]:
if not seen[v]:
seen[v] = True
stack.append((v, u))
elif v != parent:
return True # a second route into v
return False
Reaching an already-seen node by any edge other than the one you arrived on means two distinct routes reach it, which is a cycle. Cost is O(V + E), the same as any traversal.
One caveat: skipping by parent node is not the same as skipping the parent edge. If the input can contain the edge u–v twice, that pair really is a cycle of length two, and the node check misses it. When parallel edges are possible, carry the edge index rather than the parent id.
Directed: two states are not enough
Try the undirected instinct on a diamond — A→B, A→C, B→D, C→D. DFS visits A, B, D, backtracks, visits C, and sees D already marked. A "visited means cycle" rule fires. There is no cycle: D was finished long before C reached it.
The fix is to distinguish "still on the current path" from "finished". Three colours:
- white — not yet visited
- grey — entered, its descendants are still being explored
- black — entered and fully finished
An edge to a grey node is a back edge: the target is an ancestor on the path you are standing on, so following it closes a loop. An edge to a black node is a cross or forward edge to a branch that is already done — no cycle.
WHITE, GREY, BLACK = 0, 1, 2
def has_cycle_directed(graph, n):
colour = [WHITE] * n
def visit(u):
colour[u] = GREY
for v in graph[u]:
if colour[v] == GREY:
return True
if colour[v] == WHITE and visit(v):
return True
colour[u] = BLACK
return False
return any(colour[u] == WHITE and visit(u) for u in range(n))
Each node is coloured grey once and black once, and each edge is inspected once: O(V + E).
Topological order by peeling
A topological order lists every node before all the nodes that depend on it. Kahn's method computes it by repeatedly taking a node with nothing left waiting on it:
from collections import deque
def topo_order(graph, n):
indeg = [0] * n
for u in range(n):
for v in graph[u]:
indeg[v] += 1
q = deque(u for u in range(n) if indeg[u] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else None # None means a cycle
The count check at the end is the cycle detector, and it is free. If the loop stops with fewer than V nodes emitted, every remaining node still has indegree at least one from within the remaining set — each of them is waiting on another survivor. Follow those waiting-on edges backwards and, since the set is finite, you must revisit a node: a cycle. Building the indegree array is O(V + E) and the peel touches each edge once, so the whole thing is O(V + E).
The DFS alternative
Run the three-colour DFS and append each node to a list at the moment it turns black. Every descendant of a node is appended before it, so the reversed list is a topological order — and the grey check reports the cycle in the same pass. Same O(V + E). The trade is recursion depth: a dependency chain of 10⁵ nodes is 10⁵ frames, well past Python's default 1,000-frame limit, so Kahn's iterative peel is the safer default.
Why acyclic is exactly the condition
Both directions are short. If the graph has a cycle, take two nodes u and v on it: the cycle says u must precede v and v must precede u, so no linear order can satisfy both. If the graph is acyclic, a node with indegree 0 always exists in any non-empty subgraph — walk backwards along in-edges and, with no cycle to land in, the walk cannot repeat a node and must stop somewhere, and where it stops has indegree 0. So the peel never stalls and always emits all V nodes.
A valid order exists exactly when the graph is a DAG, which is why "can this be scheduled" and "is this acyclic" are the same question.
The dependency framing
Every place this shows up has the same shape: an edge from a prerequisite to the thing that needs it. Courses and their prerequisites. Build targets and their inputs. Package installs, where the resolver emits an order or reports a circular dependency — which is the count check, phrased as an error message. Spreadsheet cells and their formulas.
One extra number falls out of the peel. Process the queue in layers instead of one node at a time and the number of layers is the length of the longest chain — the minimum number of semesters, or build rounds, if unlimited work can happen in parallel within a round.
In an interview
Say which cycle rule you need before you write the loop: "the graph is directed, so a plain visited set gives false positives on a diamond — I need grey and black." Naming the diamond counterexample in one sentence is worth more than a correct implementation with no explanation, because it shows the rule is understood rather than memorised.
For ordering, start from Kahn and mention that the cycle check is the same code: "if the output is shorter than V, what is left is a cycle." Two answers from one pass is the kind of economy that reads as finding the waste.
The mistake that loses points: using the undirected parent check on a directed graph, or a plain visited set on a directed one. Both compile, both return plausible answers, and both are wrong on inputs the interviewer will reach for immediately.
Check yourself
A directed graph has A→B, A→C, B→D and C→D. A candidate reports a cycle. What did they use, and what should they have used?
A two-state visited set: D is reached from B and then again from C, and the second arrival looks like a repeat. The three-colour rule sees D as black — finished, not on the current path — and correctly reports no cycle.
Kahn's peel emits 7 of 10 nodes. What do you know about the other three?
Each of them still has an incoming edge from another of the three, so following those edges backwards inside a finite set must repeat a node. The remaining subgraph contains a cycle, and no valid order exists.
You are handed an undirected edge list that may contain the pair (3, 7) twice. Your parent-skip DFS returns False. Is that right, and what one change fixes it?
No. Two copies of 3–7 are two distinct edges between the same pair, which is a cycle of length two. The DFS steps 3 → 7 carrying parent 3, reaches 3 again along the second copy, compares v = 3 against parent = 3 and discards it as the edge it arrived on — so it skips a real cycle, not a re-read. The change is to carry the edge index down instead of the parent node id and skip only that index; the second copy has a different index and is reported. The alternative call is to decide up front that a repeated pair is one edge and dedupe the input, in which case False is right — but that is a decision to state, not to leave to the bug.