Does a dependency graph contain a loop?

Depth-first search with three states: not visited, in progress (on the current path), done. Reaching an in-progress package means the path loops back. Use an explicit stack so long dependency chains do not hit the recursion limit. O(V + E) time and space.

A 'done' package is safe to reach again: no loop goes through it.

Kahn's in-degree method answers the same question; DFS also gives a loop to report.

Build tools use this to report circular imports.

def has_loop(n: int, deps: list[list[int]]) -> bool:
    needs: list[list[int]] = [[] for _ in range(n)]
    for a, b in deps:
        needs[a].append(b)
    state = [0] * n  # 0 new, 1 on the current path, 2 finished
    for root in range(n):
        if state[root]:
            continue
        state[root] = 1
        stack = [(root, 0)]
        while stack:
            pkg, i = stack[-1]
            if i == len(needs[pkg]):
                state[pkg] = 2
                stack.pop()
                continue
            stack[-1] = (pkg, i + 1)
            dep = needs[pkg][i]
            if state[dep] == 1:
                return True
            if state[dep] == 0:
                state[dep] = 1
                stack.append((dep, 0))
    return False

Common mistakes

• Using a single visited set, which reports loops whenever two paths share a package.
• Forgetting to start DFS from every package.

Explain why two states are not enough; it is the subtle part.

Follow-up questions

Think of your answer first, then open the hint.

1. How would you print the loop?

   Show hint

   Keep the current path and slice it from the repeated package.

2. What changes for undirected graphs?

   Show hint

   Any edge to a visited node other than your parent is a loop.