Strongly Connected Components Visualizer

How it works

1. Run DFS over the whole graph and push each node onto a stack when it finishes.
2. Build the transpose graph Gᵀ by reversing every edge.
3. Take nodes in reverse finish order (the last to finish first). If a node has no component yet, start a DFS from it in Gᵀ.
4. Every node that this DFS reaches belongs to one new component.
5. Continue until every node has a component number.

Why reversing the edges works

Collapse every SCC into a single node and you get the condensation, which is always a DAG (if two components could reach each other, they would be one component). The key lemma: if an edge leads from component C to component C′, then some node of C finishes later in the first DFS than every node of C′. So the node that finishes last overall lies in a source component — one that no other component can reach.

Reversing every edge turns that source into a sink: a DFS started from it in Gᵀ cannot escape, so it collects exactly that one component. Mark it as done, take the next unassigned node in reverse finish order, which lies in a source of what remains, and repeat. Each second-pass search peels off exactly one SCC.

Worked example

The page opens on three clusters joined by one-way bridges: A → B, B → C, C → A, C → D, D → E, E → D, E → F, F → G, G → H, H → F.

• Pass 1: DFS from A runs A → B → C → D → E → F → G → H. Nodes finish in the order H, G, F, E, D, C, B, A, so A finishes last.
• Reverse every edge. The bridge C → D becomes D → C, so a search starting at A can no longer cross it.
• Pass 2 from A in Gᵀ reaches C and B: component {A, B, C}. The next unassigned node in reverse finish order is D, which reaches E: {D, E}. Finally F reaches H and G: {F, G, H}.

The condensation is the chain {A, B, C} → {D, E} → {F, G, H}: inside a cluster you can go anywhere, but once you cross a one-way bridge there is no way back.

Kosaraju vs Tarjan

Tarjan's algorithm finds the same components with a single DFS. It gives every node a discovery index and a low-link value — the smallest index it can reach, through its subtree and one more edge, among nodes still on the stack — and keeps visited nodes on a stack; when a node's low-link equals its own index, it is the root of an SCC and everything above it on the stack is popped off as one component. Tarjan needs no transposed graph, so it uses less memory and is usually faster in practice, and it outputs components in reverse topological order.

Kosaraju's algorithm is easier to understand and to get right: two plain DFS passes and an edge reversal. Both run in O(V + E). The same low-link idea also finds bridges and articulation points in undirected graphs.

Common mistakes

• Running the second pass on the original graph instead of the transpose: the search leaks across bridges and merges components.
• Using discovery order or plain finish order instead of reverse finish order for the second pass.
• Confusing SCCs with weakly connected components, which ignore edge direction and can be found with plain BFS or union-find.
• Deep recursion on large graphs: both passes may need an explicit stack.
• Forgetting single nodes: a node on no cycle is an SCC by itself, so in a DAG every node is its own component.

Where SCCs are used

• 2-SAT: build the implication graph; the formula is satisfiable exactly when no variable x shares an SCC with ¬x.
• Dependency analysis: every SCC with more than one node is a circular dependency between modules or packages, and mutually recursive functions form SCCs of a program's call graph.
• Condensation + DP: collapsing SCCs turns any directed graph into a DAG, so topological sort and DAG dynamic programming can run on it.
• Network analysis: the web graph's famous "bow-tie" shape has a giant SCC at its core; SCCs also reveal groups of accounts that all follow each other.
• Model checking and deadlock detection: cycles of states or of processes waiting on each other appear as non-trivial SCCs.

Time and space complexity

Strongly Connected Components in Python

def kosaraju(graph):
    """graph: {node: [successors]}. Returns comp[v] = component number (0, 1, ...)."""
    visited, finish = set(), []            # finish: the finish stack

    def dfs1(u):
        visited.add(u)                     # mark u visited
        for v in graph[u]:
            if v not in visited:
                dfs1(v)
        finish.append(u)                   # push u on the finish stack

    for u in graph:
        if u not in visited:
            dfs1(u)

    gt = {v: [] for v in graph}            # G^T: reverse every edge
    for u in graph:
        for v in graph[u]:
            gt[v].append(u)

    comp = {}

    def dfs2(x, c):                        # in G^T
        comp[x] = c
        for y in gt[x]:
            if y not in comp:
                dfs2(y, c)

    c = 0
    for u in reversed(finish):             # reverse finish order
        if u not in comp:
            dfs2(u, c)
            c += 1
    return comp

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• DFS Visualizer — Depth-First SearchDepth-first search explores a graph by going as deep as possible, then backtracking. See DFS step by step with discovery and finish times, back edges and code.
• Topological Sort VisualizerA topological sort orders the nodes of a DAG so every edge points forward. Watch Kahn's algorithm step by step, see why cycles block it, and get the code.
• BFS Visualizer — Breadth-First SearchBreadth-first search explores a graph level by level with a queue and finds fewest-edge paths. Watch BFS run step by step, with code and O(V + E) analysis.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.