Cycle Detection in Graphs

Cycle detection prevents invalid schedules and infinite loops—undirected: back edge to non-parent; directed: revisit node on recursion stack (gray).

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

While building edges, Union-Find detects cycle if endpoints already connected (undirected). Directed: three colors white/gray/black in DFS.

Try this in Python

def dfs(adj: list[list[int]], start: int) -> list[int]:
    seen = set()
    order: list[int] = []

    def go(u: int) -> None:
        seen.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                go(v)

    go(start)
    return order


print(dfs([[1, 2], [0], [0]], 0))

Common mistakes

• Treating undirected back edge to parent as cycle.
• Missing cycle in functional graphs (tortoise-hare different topic).

Key takeaways

• Topo sort fails ⟺ directed cycle exists.
• Greedy scheduling often needs acyclic constraint graph.