Cycles & Ordering

Everything here builds on the DFS from Traversal: cycle detection (directed and undirected), topological sort, and union-find are three separate-looking tools that all trace back to the same idea - a cycle is a back edge, nothing more exotic than that.

1. Cycle detection: the core idea

A plain 2-state visited set does exactly one thing: it guarantees termination by refusing to re-recurse into a node. What it cannot do is tell you why a node was re-seen:

• re-seen because it's still on my current path → that's a cycle
• re-seen because it's already finished → harmless convergence, not a cycle

Those two cases need a second axis of information that plain visited doesn't carry. The fix is to track three states instead of two - WHITE (never seen), GRAY (on the current DFS stack, i.e. mid-recursion), BLACK (fully finished, backed all the way out) - and classify every DFS edge by the colour of the node it lands on:

Neighbour colour	Meaning	Edge type	Cycle?
WHITE (unseen)	recurse into it	tree edge	no
GRAY (on the current DFS stack)	points back to an ancestor	back edge	YES
BLACK (fully finished)	converged onto a done subtree	forward/cross edge	no

Mnemonic

"Plain visited STOPS loops (termination); the second axis DETECTS them (a cycle)."

⚠

A cycle exists iff DFS hits a GRAY node

A cycle exists iff DFS finds an edge to a GRAY node. That one rule covers both directed and undirected graphs - they only differ in which colours can occur.

2. Cycle detection: directed vs undirected

Directed = one-way streets. Undirected = two-way streets.

This is why the two algorithms below look different even though they share the same underlying rule.

Directed - watch the STACK. You need all 3 colours, because an edge to a BLACK (finished) node is not a cycle (it's convergence) - to tell that apart from a real back edge you must distinguish GRAY from BLACK. And you must not skip the parent: A→B plus B→A are two distinct directed edges, which is a real 2-cycle.

from collections import defaultdict

 

def has_cycle_directed(graph):

WHITE, GRAY, BLACK = 0, 1, 2

status = defaultdict(int) # default WHITE

def dfs(node):

status[node] = GRAY # on the stove

for nb in graph[node]:

if status[nb] == GRAY: return True # back edge -> cycle

if status[nb] == WHITE and dfs(nb): return True

status[node] = BLACK # served & safe (the UN-graying)

return False

return any(status[n] == WHITE and dfs(n) for n in graph)

No if here ever tests for BLACK. So what is status[node] = BLACK for? Setting a node BLACK is the un-graying - it takes the node off the stove so it stops testing positive for GRAY once you've backed out of it. Delete that one line and a plain DAG (e.g. a diamond) false-positives, because the converged node stays wrongly GRAY forever. You never test for black directly; black is only how a node stops testing as gray.

Undirected - watch the DOOR (where you came from), not the stack. A plain visited set suffices here: undirected DFS never produces cross/forward edges, so any visited non-parent neighbour is guaranteed to be a GRAY ancestor. Just skip the edge back to your parent.

def has_cycle_undirected(graph):

visited = set()

def dfs(node, parent):

if node in visited: return True # check-on-entry (mark-on-pop twin)

visited.add(node)

for nb in graph[node]:

if nb != parent and dfs(nb, node): return True

return False

return any(n not in visited and dfs(n, -1) for n in graph)

The mnemonic that fixes the repeated inversion of the 2-cycle question:

Mnemonic

U-TURN vs ROUNDABOUT. Walking one undirected edge back the way you came is a U-turn - one edge, innocent - and that's exactly what parent-skip skips. Two directed edges A→B, B→A are a roundabout - two distinct edges, a real 2-cycle - which is exactly why directed must not skip the parent. The definition underneath: a cycle exists when a node on the path is reached from an entirely separate edge.

Mnemonic

"Gray for one-way, Parent for two-way." Parent-skip is a feature in undirected and would be a bug in directed.

The highlighted edge C -> A lands on a GRAY vertex - a back edge, so this is a cycle.

The BFS versions of both

Nothing about cycle detection is inherently depth-first - what DFS gives you for free is the current path, and BFS can carry that same information explicitly.

Undirected, breadth-first. The parent is the only thing the DFS version needed, and a queue can hold it: enqueue (node, parent) tuples instead of bare nodes. Everything else is the traversal from Traversal unchanged.

from collections import deque

 

def has_cycle_undirected_bfs(graph):

visited = set()

for src in graph:

if src in visited:

continue

visited.add(src)

q = deque([(src, -1)]) # (node, the node that discovered it)

while q:

node, parent = q.popleft()

for nb in graph[node]:

if nb == parent:

continue # the U-turn back down the edge we arrived on

if nb in visited:

return True # reached from a second, separate edge -> cycle

visited.add(nb)

q.append((nb, node))

return False

Directed, breadth-first. There is no tuple trick here, because the thing that makes a directed cycle is "still on the current path," and BFS has no current path. The BFS answer is a different algorithm entirely - Kahn's, in the next section - which detects a cycle by noticing that some vertices can never have their in-degree reach zero.

Mnemonic

Undirected BFS carries the parent in the queue; directed BFS gives up on paths and counts in-degrees instead. Same split as before: undirected needs one edge of history, directed needs the whole path - and only DFS gets the whole path for free.

3. The DFS tree and the four kinds of edge

The colour table in section 1 named two of the four edge types and lumped the rest together as "not a cycle." Here is the complete picture, because the missing pieces are what several later algorithms are built on.

A DFS does not just visit vertices - it imposes a tree on the graph. Every time DFS recurses from u into an unvisited v, that edge becomes a tree edge, and those tree edges form a spanning forest of everything reachable. Every other edge of the graph points somewhere inside that forest, and where it points is fully determined by two timestamps per vertex:

• disc[u] - the step at which u was discovered (turned GRAY)
• fin[u] - the step at which u finished (turned BLACK)

def dfs_times(graph):

disc, fin, clock = {}, {}, [0]

def dfs(u):

disc[u] = clock[0]; clock[0] += 1

for v in graph[u]:

if v not in disc:

dfs(v) # tree edge

fin[u] = clock[0]; clock[0] += 1

for u in graph:

if u not in disc:

dfs(u)

return disc, fin

Edge u -> v	Test at the moment DFS looks at it	Means
Tree edge	v is WHITE - you are about to recurse into it	v is a child of u in the DFS tree.
Back edge	v is GRAY	v is an ancestor of u: still on the recursion stack. This is a cycle.
Forward edge	v is BLACK and disc[u] < disc[v]	v is a descendant of u, reached earlier by a longer route. A shortcut down your own subtree.
Cross edge	v is BLACK and disc[u] > disc[v]	v is in a different, already-finished subtree - neither ancestor nor descendant.

⚠

Undirected DFS has no forward or cross edges

An undirected DFS has no forward or cross edges at all. That is not a coincidence, it is a theorem, and it is the real reason undirected cycle detection can get away with a plain 2-state visited set. Suppose an undirected DFS at u sees a finished neighbour v. Then the edge {u,v} was already in v's adjacency list while v was being explored, so v either recursed into u (making it a tree edge) or found u GRAY (making it a back edge). There is no third option. In a directed graph the edge u -> v gives v no such opportunity, and that is where the other two types come from.

Mnemonic

The four types are just "where in the DFS tree does the arrow land": down one step (tree), up (back), down several steps (forward), sideways (cross). Only "up" is a cycle, because only "up" points at something you have not finished yet.

The timestamps are worth more than the edge names. Three facts fall out of them and each one powers an algorithm:

• Nesting. For any two vertices, the intervals [disc, fin] are either disjoint or one fully contains the other - never partially overlapping, because recursion returns in reverse order of entry. Containment is exactly the ancestor relation, so "is v a descendant of u" is the O(1) test disc[u] < disc[v] and fin[v] < fin[u].
• Postorder ranks the vertices. fin[u] > fin[v] for every tree, forward and cross edge u -> v, and only back edges break it - so on a DAG, descending finish time is a topological order (section 6).
• Low-link. "The earliest disc reachable from my subtree" is what Tarjan's SCC algorithm tracks, and it is only computable because back edges are distinguishable from cross edges (MST & SCC).

4. Topological sort: Kahn's algorithm

Getting dressed.

Socks before shoes, pants before belt. The topological order is the single sequence you put every garment on - and unrelated garments (socks vs shirt) both still appear, in some order, even though neither depends on the other.

The misconception to hit head-on before writing any code: a topological order is a LINEUP, not a WALK. Consecutive nodes in the order need not be adjacent in the graph.

Mnemonic

Lay every node on a line left-to-right; the order is valid iff every edge points RIGHT. For A→C, B→C, C→D: A, B, C, D is valid even though A→B is not an edge. Two disconnected nodes X, Y have a valid topo order (X,Y or Y,X) yet no path between them at all. A path requires adjacency between consecutive nodes; a lineup does not.

Kahn's algorithm builds that lineup by tracking each node's in-degree as a wait count: how many prerequisites it's still waiting on. 0 means free to place right now. Placing a node lets everyone waiting on it cross a name off their own list, and a node only joins the ready pool once its last blocker leaves.

from collections import deque

 

def topological_sort(graph):

indeg = {u: 0 for u in graph}

for u in graph:

for v in graph[u]:

indeg[v] += 1

pool = deque(u for u in graph if indeg[u] == 0) # everyone free at the start

order = []

while pool:

u = pool.popleft()

order.append(u)

for v in graph[u]:

indeg[v] -= 1 # cross u off v's wait list

if indeg[v] == 0: # v's LAST blocker just left

pool.append(v)

return order if len(order) == len(graph) else None # see the next section

Mnemonic

The pool can be a queue, a stack, a heap - the container only picks which valid order you get, never whether it's valid.

A topological order only exists for a DAG (a directed acyclic graph), and that single requirement is why the same algorithm answers four different-looking questions:

• Course prerequisite scheduling - which order can these courses be taken in
• Build dependency resolution - which order can these targets be compiled in
• Task scheduling with dependencies - which order can this work be done in
• Cycle detection in a directed graph - covered in the next section: if no valid order exists, the graph is not a DAG, so it has a cycle

5. Topological sort: detecting cycles

The tempting-but-wrong cycle test is "the pool started empty → cycle." That only catches graphs with no free node at all. It misses graphs where the pool starts non-empty and only empties partway, leaving nodes stranded.

Trace A→B, B→C, C→B: the pool starts as [A] (non-empty!). You place A, then B and C are stuck waiting on each other forever. The pool drains with B and C never placed.

Mnemonic

"Count the LINEUP, not the pool." If len(order) < n when the pool runs dry, the leftovers are all waiting on each other - a deadlock, which is exactly what a cycle looks like from Kahn's point of view.

That single integer comparison (len(order) == len(graph), already in the code above) gives you LC 207 Course Schedule for free - it's the same cycle detection from section 2, wearing a scheduling story.

6. Topological sort: the DFS postorder version

Kahn's algorithm builds the order front-to-back by repeatedly asking "who has no prerequisites left." DFS builds the same kind of order back-to-front, and needs no in-degree array at all - it just uses the fact from section 3 that a vertex finishes after everything reachable from it.

from collections import defaultdict

 

def topological_sort_dfs(graph):

WHITE, GRAY, BLACK = 0, 1, 2

status = defaultdict(int)

order = []

def dfs(u):

status[u] = GRAY

for v in graph[u]:

if status[v] == GRAY:

return False # back edge -> cycle -> no order exists

if status[v] == WHITE and not dfs(v):

return False

status[u] = BLACK

order.append(u) # POSTORDER: after every dependent

return True

for u in list(graph):

if status[u] == WHITE and not dfs(u):

return None

order.reverse() # postorder is the order BACKWARDS

return order

Postorder records "I am done, and so is everything downstream of me."

So the first thing appended is a vertex with nothing after it - the last thing in a valid order. Appending in finish order therefore builds the answer backwards, and one reverse() at the end turns it around. It is the same "record dead ends, then reverse" shape as Hierholzer's algorithm and Kosaraju's first pass.

⚠

Preorder append gives a wrong topological order

Appending in preorder instead of postorder gives a wrong answer that looks plausible. Move order.append(u) above the neighbour loop and you get "discovery order," which on a simple chain happens to be correct and on a diamond is not: from A with A->B, A->C, B->D, C->D, preorder can emit A, B, D, C - and C must come before D. The whole guarantee lives in appending on the way out, not the way in.

Both algorithms are O(V + E) and both detect cycles, so the choice comes down to the practicalities:

	Kahn's (BFS)	DFS postorder
Extra bookkeeping	an in-degree array	nothing beyond the 3-colour status
Cycle detection	len(order) < n after the pool drains	an edge to a GRAY vertex, caught the instant it happens
Recursion limit	none - fully iterative	dies past ~1000 frames in Python on a long chain
Lexicographically smallest order	free: make the pool a min-heap	not directly expressible
Level / "how many rounds" info	free: process the pool one full generation at a time (LC 1136 Parallel Courses)	not available
Reports which vertices are stuck	yes - whatever never got placed	yes - but you must record the GRAY path yourself

Mnemonic

Kahn if you need the order's shape (levels, lexicographic, no recursion); DFS if you just need an order. Interviews ask for Kahn slightly more often because in-degree counting is easier to explain out loud, and because "how many semesters" style follow-ups are free with it.

7. What a topological order buys you

A topological order is rarely the answer by itself - it is the setup. Once the vertices are laid out so every edge points forward, any quantity that propagates along edges can be computed in a single left-to-right pass, because everything a vertex depends on is already final by the time you reach it.

Counting paths. How many distinct paths run from start to target in a DAG? Exponentially many, potentially - but counting them is linear:

def count_paths(adj, topo_order, start, target):

ways = {u: 0 for u in topo_order}

ways[start] = 1

for u in topo_order:

if ways[u]: # nothing to propagate from an unreachable u

for v in adj[u]:

ways[v] += ways[u] # every path into u extends into v

return ways[target]

Longest path, which is NP-hard on a general graph, is the same pass with max instead of + - see Shortest Paths on a DAG.

Mnemonic

On a DAG, "propagate along edges in topological order" replaces recursion with a loop. Counting paths, longest/shortest path, reachable-set sizes, earliest/latest start times in a schedule - all the same three lines with a different combining operator. This is also exactly what memoised recursion on a DAG is, with the memo table filled bottom-up instead of on demand.

Levels: how many rounds. Kahn's pool naturally holds one full generation at a time. Drain it by generation instead of one vertex at a time and the loop count is the length of the longest dependency chain - "how many semesters," "how many build stages," "how many rounds of parallel work."

from collections import deque

 

def min_rounds(adj, indeg, num_nodes):

pool = deque(u for u in range(num_nodes) if indeg[u] == 0)

placed, rounds = 0, 0

while pool:

rounds += 1

for _ in range(len(pool)): # snapshot the size: THIS generation only

u = pool.popleft()

placed += 1

for v in adj[u]:

indeg[v] -= 1

if indeg[v] == 0:

pool.append(v)

return rounds if placed == num_nodes else -1

⚠

Snapshot pool length before the inner loop mutates it

for _ in range(len(pool)) must snapshot the length before the inner loop appends to it. Writing while pool: for the inner loop instead collapses every generation into one, and the round count comes out as 1 on any connected DAG. This is the same fixed-size-inner-loop idiom as level-order tree traversal, and it fails the same way when the size is re-read each iteration.

The critical path. Give every task a duration and the same two passes compute a project schedule. A forward pass in topological order gives each task its earliest start (the longest path of prerequisites reaching it); a backward pass gives its latest start without delaying the project. The difference is that task's slack, and the tasks with zero slack form the critical path - the chain that sets the total duration, and the only tasks where a one-day delay costs the project a day.

def critical_path(adj, rev_adj, order, duration):

earliest = {u: 0 for u in order}

for u in order: # FORWARD: prerequisites first

for v in adj[u]:

earliest[v] = max(earliest[v], earliest[u] + duration[u])

 

total = max(earliest[u] + duration[u] for u in order)

latest = {u: total - duration[u] for u in order}

for u in reversed(order): # BACKWARD: dependents first

for p in rev_adj[u]:

latest[p] = min(latest[p], latest[u] - duration[p])

 

return total, [u for u in order if earliest[u] == latest[u]] # zero slack

Mnemonic

Earliest start is a longest path; slack is the gap between the two passes. That makes the critical path a longest-path problem, which is only tractable because the graph is a DAG - the same asymmetry as longest path on a DAG. Shortening a non-critical task changes nothing; that is what "slack" means.

Uniqueness. Sometimes the question is not "give me an order" but "is the order forced?" (LC 444 Sequence Reconstruction). Kahn's answers it for free: the order is unique exactly when the pool holds exactly one vertex at every step. Two vertices in the pool at once means two valid orders exist, because either could go next.

A unique topological order means the DAG has a Hamiltonian path.

If the order is forced, then consecutive vertices in it must be joined by an edge - otherwise you could swap them - and a path through every vertex in sequence is precisely a Hamiltonian path (Eulerian & Hamiltonian). It is easy to check here only because the graph is a DAG, where the topological order hands you the single candidate ordering to test.

Lexicographically smallest order. Replace the pool's deque with a heapq and every step takes the smallest available vertex. This is greedy and it is correct: taking the smallest currently-free vertex can never make a smaller vertex unavailable later, because nothing already free can become blocked.

⚠

Lexicographic topo order isn't "just sort"

"Lexicographically smallest topological order" is not "sort the vertices and check." Sorting ignores the constraints entirely; the greedy heap respects them. And the reverse-direction question - lexicographically smallest order where you may not reorder freely, such as "smallest sequence such that every edge points forward, processed from the back" - needs the max-heap on the reverse graph, then a reverse. Getting that backwards is a classic wrong answer on an otherwise-correct implementation.

8. Union-Find: groups and leaders

Union-find is its own data structure with its own subject page - Disjoint Sets covers the internals (union by rank, array vs hashmap backing, the complexity argument) and the advanced variants: parity DSU for "opposite sides", weighted DSU for ratios, and rollback DSU. What follows here is only what the graph algorithms on this site need from it - the two graph questions it answers, and the three bugs that break those answers.

GROUPS and LEADERS.

Each member stores only their immediate boss (a parent pointer). The leader of a group is whoever is their own boss. find climbs the boss chain up to the leader; union makes the losing leader report to the winning one. Why not have everyone store their leader directly, no chain? Because then a merge would have to relabel the entire losing group - O(size) every time. The boss-pointer scheme makes union O(1): only the losing leader's own record changes.

class UnionFind:

def __init__(self):

self.leader = {}

self.size = {}

 

def find(self, node):

if node != self.leader.setdefault(node, node): # lazy: register on first sight

self.leader[node] = self.find(self.leader[node]) # path compression

return self.leader[node]

 

def union(self, a, b):

ra, rb = self.find(a), self.find(b)

if ra == rb:

return False # already same group -> redundant edge / cycle

sa = self.size.setdefault(ra, 1)

sb = self.size.setdefault(rb, 1)

if sa < sb: # small joins large

ra, rb = rb, ra

self.leader[rb] = ra # loser's LEADER points at winner's leader

self.size[ra] += self.size[rb] # absorb the WHOLE roster

return True

Three bugs worth the anchor that kills each:

⚠

Union by size adds to the wrong side

size[winner] += 1 instead of += size[loser]. Insidious - it's accidentally correct whenever the loser is a singleton, so it hides until you merge a group with real members. On a stream where the loser has 2 members, += 1 prints one too few. Anchor: the merger acquired the company but only put the CEO on payroll - absorb the whole ROSTER.

⚠

Path compression can no-op silently

Path-compression rebinding no-op. Writing node = self.find(self.leader[node]) rebinds the local name to the root, then self.leader[node] = node stamps the root's own record (a no-op). Compression silently vanishes while every test still passes (find is still correct). Anchor: you gave the CEO the CEO's speed-dial - the member who called never got the number. Fix: each frame must write the returned root into its own node's entry while node still means the caller (the one-liner above does this).

⚠

Union must link leaders, not endpoints

Union links the ENDPOINTS, not the leaders. union(a, b) must point find(b)'s leader at find(a)'s leader - never b at a directly. Linking the raw endpoints corrupts the forest.

Mnemonic

Lazy unions build a CONGA LINE (the skewed-BST disease - find degrades to O(n)). Small-joins-large: depth only grows when you lose, and losing at least doubles your group, so height ≤ log₂n. Path compression: climb once, and everyone you passed gets the leader's speed-dial. Together ≈ O(1) amortised (inverse Ackermann ≤ 5).

9. Union-Find: counting components

A tempting wrong idiom: a find-only comprehension with no union call. find without union is diagnosis without treatment - nothing ever merges, so the count is meaningless.

The fix uses union's boolean return value as the counter. Start with n one-person groups; every union that returns True fuses two groups into one, retiring exactly one leader; a False (endpoints already share a group) retires nobody.

def count_components(n, edges):

uf = UnionFind()

return n - sum(uf.union(u, v) for u, v in edges) # True sums as 1

Mnemonic

"Count the retired leaders." components = n - (number of successful unions). Exact because every merge takes two groups in and puts one out - never two, never zero.

⚠

A False union return means a redundant edge

A False return means the edge is redundant - both endpoints were already connected, so this edge closes a cycle. That's the entire answer to LC 684 Redundant Connection: the edge whose union returns False.

10. Extracting the cycle, not just detecting it

Everything above answers "is there a cycle" with a boolean. Plenty of problems want the cycle itself - which courses form the deadlock, which edge closed the loop, which sequence of trades is the arbitrage. The extraction is cheap once you notice that the GRAY set is the current path, so if you keep it in a list rather than a status map, the cycle is a suffix of that list.

from collections import defaultdict

 

def find_cycle_directed(graph):

WHITE, GRAY, BLACK = 0, 1, 2

status = defaultdict(int)

path, pos = [], {} # path = the GRAY stack, in order

 

def dfs(u):

status[u] = GRAY

pos[u] = len(path)

path.append(u)

for v in graph[u]:

if status[v] == GRAY:

return path[pos[v]:] # the cycle IS the tail of the path

if status[v] == WHITE:

found = dfs(v)

if found:

return found

status[u] = BLACK

path.pop() # leaving the path, not just un-graying

del pos[u]

return None

 

for u in list(graph):

if status[u] == WHITE:

found = dfs(u)

if found:

return found

return None

⚠

path.pop() must match where status = BLACK happens

path.pop() must happen on the way out, in the same place status = BLACK does. The list and the status map are two views of the same fact - "am I on the current path" - and letting them disagree is the whole bug class. Forget the pop() and path becomes a preorder log rather than a stack, so the slice returns vertices that are not on the cycle at all.

⚠

Use a recorded position, not path.index(v)

Use a recorded position, not path.index(v). index is a linear scan, so on a long path it turns the extraction into O(V) per back edge and the whole DFS into O(V * E). The pos dict keeps it O(1), at the cost of one more line in the del on exit - and forgetting that del leaves stale positions that slice from the wrong place.

Undirected extraction is the same code with parent-skip instead of the three colours: path is still the DFS stack, and reaching an already-on-path non-parent neighbour still means the cycle is the suffix from that vertex.

With union-find, extraction is free and needs no DFS at all: the edge whose union returns False is the edge that closed a cycle (section 9). That gives you the closing edge immediately; recovering the full cycle then means one BFS between its two endpoints in the graph built from the edges accepted so far.

Mnemonic

Detect with a colour, extract with a list. Any "which vertices form the loop" question is the boolean version plus one list you were already maintaining implicitly on the call stack.