Cycles, topological order and union-find

Why it matters

Ordering and grouping questions appear wherever there are dependencies: course prerequisites, package managers and build tools, job schedulers, spreadsheet recalculation, and deadlock detection on a wait-for graph. Interviewers use them to check that you know which questions a directed graph can answer, that you detect cycles without false positives, and that you reach for union-find when connectivity grows edge by edge. In infrastructure work the same reasoning shows up in workflow engines and deployment tools that must apply resources in dependency order.

Core ideas

Topological order. An ordering of vertices in which every edge u -> v places u before v. It exists exactly when the directed graph has no cycle (a DAG), and it is usually not unique.

Kahn's algorithm. Compute in-degrees and enqueue every vertex with in-degree 0. Repeatedly remove a vertex, append it to the output, and decrement the in-degree of its successors, enqueuing those that reach 0. Invariant: every output vertex appears after all of its predecessors. If fewer than V vertices are output, every remaining vertex still has a predecessor among the remaining ones, which forces a cycle. Replacing the queue with a min-heap yields the lexicographically smallest order in O(V log V + E).

DFS order and directed cycles. Run DFS from every unvisited vertex and record each vertex when it finishes. For an edge u -> v in a DAG, v finishes before u, so the reversed finish order is a topological order. Keep three states: unvisited, active (on the current recursion path) and done. Reaching an active vertex is a back edge, which closes a directed cycle. Reaching a done vertex is harmless: in the diamond a -> b, a -> c, b -> d, c -> d, vertex d is reached twice with no cycle. A single visited set cannot distinguish these cases, which is the classic bug.

Undirected cycles. Each undirected edge is seen from both ends, so DFS must skip the edge back to its parent; any other visited neighbor closes a cycle. With parallel edges, skip only the specific edge you arrived on, not every edge to the parent. Applying the directed three-state rule unchanged to an undirected graph reports a false cycle as soon as DFS looks back along the edge it arrived on.

Union-find (disjoint set union). It maintains a partition under union(a, b) and find(x), which returns the representative of x's set. Each set is a tree of parent pointers.

• Union by rank or size attaches the shorter or smaller tree under the other, keeping height O(log n).
• Path compression makes every node visited by find point directly to the root.

With both, any sequence of m operations on n elements costs O(m α(n)) in total, where α is the inverse Ackermann function, at most 4 for any input you could store. The bound is amortized: an individual find can still walk a long path, but the compression it performs pays for later operations. Union by rank alone keeps every find O(log n); path compression alone gives logarithmic amortized cost.

Union-find detects cycles in undirected graphs as edges arrive: if both endpoints already share a root, the new edge closes a cycle. That is the redundant-connection pattern and the test Kruskal's algorithm uses to skip edges. Union-find cannot detect directed cycles or answer directed reachability, and it does not support deleting edges.

Common misconceptions

• "Reaching any visited vertex means a directed cycle." Only a vertex on the current DFS path signals a cycle; reaching a finished vertex is normal in DAGs with shared descendants.
• "There is one correct topological order." Many orders are usually valid, so check that every edge points forward instead of comparing with one expected list. The order is unique only when consecutive vertices are joined by edges (a Hamiltonian path).
• "Union by rank alone gives near-constant time." Rank alone gives O(log n); the inverse-Ackermann bound needs both heuristics and is amortized, not per operation.
• "Union-find can replace DFS for any connectivity question." It handles undirected, growing connectivity. It cannot give paths, answer directed reachability or undo unions without extra machinery.
• "Kahn's algorithm needs a separate cycle check." The output length is the check.

How to approach it

Name the question first. "Can all tasks be completed?" is cycle detection on a directed graph, "give an order" is a topological sort, and "same group?" or "which edge is redundant?" in an undirected setting suggests union-find. Get edge direction right before anything else: if a requires b first, the edge is b -> a. Prefer Kahn's algorithm when recursion depth could be large; prefer DFS when you must report the cycle itself. Write union-find as a small class whose union returns whether a merge happened, and reuse it. Typical follow-ups, especially at mid and senior level: edges arriving as a stream, returning the actual cycle, or running independent tasks in parallel by processing each Kahn frontier as one batch.