Kosaraju's Algorithm (Two-Pass SCC)

Strongly connected components partition a directed graph into maximal mutually reachable groups—Kosaraju (two DFS) or Tarjan (one DFS with low-link).

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)

Condensation graph (SCC DAG) simplifies many problems. Low-link low[u] detects bridges and articulation points too.

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

• Confusing SCC with weak components in undirected graphs.
• Iterative Tarjan implementation bugs.

Key takeaways

• 2-SAT and dependency cycles often use SCC.
• Practice Kosaraju first, then Tarjan for one-pass.