Workspace

Problem workspace

3 day streakD

Kosaraju’s Algorithm

HardGraphsConnectivity

The challenge

Partition a directed graph into strongly connected components (SCCs), where every vertex inside one component can reach every other vertex in it.

Uses two DFS passes and a transpose graph with every directed edge reversed.

Example

The example has SCCs {A, B, F}, {C, D}, and {E}. On a DAG, every vertex is its own SCC.

Use the walkthrough below to inspect the input and each state change.

See Kosaraju, step by step

Follow the edges. Watch the state change.

Directed · 6 vertices · 7 edgesA = 0, B = 1, …
Three SCCsDirected graph with 6 vertices. Pass 1: compute finishing order. Run DFS over every vertex in the original directed graph. Append a vertex only after all its neighbors finish. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisitedLabels identify components or colors
Step 01 / 15

Pass 1: compute finishing order.

Run DFS over every vertex in the original directed graph. Append a vertex only after all its neighbors finish.

for each unseen vertex: dfs1(vertex)

Finish order · latest last

Empty
View input edges

A → B · B → F · F → A · B → C · C → D · D → C · D → E

Put it into code

Finishing order puts components in the right sequence for exploration on the reversed graph.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

def kosaraju(adj):
    n = len(adj)
    seen, finish = [False] * n, []

    def dfs1(u):
        seen[u] = True
        for v in adj[u]:
            if not seen[v]:
                dfs1(v)
        finish.append(u)  # Postorder, NOT discovery order.

    for u in range(n):
        if not seen[u]:
            dfs1(u)
    transpose = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            transpose[v].append(u)
    seen = [False] * n
    components = []

    def dfs2(u, component):
        seen[u] = True
        component.append(u)
        for v in transpose[u]:
            if not seen[v]:
                dfs2(v, component)

    for u in reversed(finish):
        if not seen[u]:
            component = []
            dfs2(u, component)
            components.append(component)
    return components

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap