A call-graph dashboard paints six services as one “connected” blob. The code Union-Finds every RPC as an undirected edge. Checkout can reach Inventory; Inventory cannot reach Checkout. The rollback playbook assumes mutual reachability and pages the wrong team. Nobody “forgot a graph library.” They ran undirected components on a directed graph.

u and v are strongly connected when each can reach the other — Kosaraju finds those blocks with two DFS passes and a transpose; the condensation is a DAG. The layout is a directed adjacency list (Graphs). Finish times and the explicit stack live on DFS. Families and the catalog live on the Algorithms Roadmap. It is not Union-Find of an undirected friendship graph, not 3-color cycle detection, and not a reason to re-teach Kahn.

Both directions, or it is not strong

An edge u → v is one-way reachability. Strong connectivity asks for a path u ⇝ v and a path v ⇝ u. Mutual retries A → B → A are one block. A one-way call into a leaf is not.

Undirected “same component” is a different job: a walk, or Union-Find. Dropping arrowheads glues Checkout to Inventory because some edge exists. That is not strong connectivity. A cycle of size two or more sits inside an SCC — the tests that prove a back edge live on Cycle Detection, not here. A vertex with no return path is still an SCC of size one.

Note: Reachability from a source is “who can I call.” Strong connectivity is “who is in my mutual blast radius.” Do not answer the second with the first.

Kosaraju: finish, flip, finish again

Two DFS forests and one reversed edge set. You already own finish times; this post does not re-derive the walk or the leaving marker.

  1. Finish order. DFS-forest the original digraph. Push each vertex onto a stack when it finishes (after every descendant in this walk has left).
  2. Transpose. Reverse every edge. u → v becomes v → u. Same vertex set.
  3. Second forest. DFS the transpose, always starting at the next unused vertex from the top of the finish stack (reverse finish order). Each tree you grow is one strongly connected component.

The first pass orders the vertices. The transpose turns paths out of a cluster into paths in. Seeded in reverse finish order, the second walk cannot leave the cluster — so the tree is the SCC.

Do not skip the transpose and DFS the original graph in reverse finish order. Reverse finish on a DAG is topological sort; on a cyclic digraph without the flip, the trees are not the components.

Note: The first pass is a forest. Loop every vertex. Starting only at a source misses SCCs that source cannot reach. Recursion is lecture-sized; an ArrayDeque with a leaving marker is the same finish stamp — the DFS post owns that stack.

A walked pass: two cycles and a bridge

Five vertices. Cycle A → B → C → A, a one-way bridge C → D, cycle D ⇄ E. C’s neighbors are A, then D. Forest starts at A.

  A → B → C → A
          |
          v
          D ⇄ E

adj:  A:[B]  B:[C]  C:[A, D]  D:[E]  E:[D]

dfs(A)
  dfs(B)
    dfs(C)
      neighbor A: already started — skip
      dfs(D)
        dfs(E)
          neighbor D: already started — skip
          finish E @1
        finish D @2
      finish C @3
    finish B @4
  finish A @5

finish stack (top = last finished):  A, B, C, D, E

Transpose: flip every arrow. Second DFS on G^T, pop the finish stack, skip assigned vertices.

G^T:  A:[C]  B:[A]  C:[B]  D:[C, E]  E:[D]
      (bridge flipped: D → C)

pop A  unseen → dfs_T(A) → C → B     tree {A, C, B}   component 0
pop B  assigned
pop C  assigned
pop D  unseen → dfs_T(D) → E         tree {D, E}      component 1
pop E  assigned

Two trees, two SCCs. The bridge C → D is one-way, so the clusters did not merge. Isolated vertex: first pass finishes it, second pass assigns a singleton. Empty graph: both forests no-op.

Condensation. One supervertex per component. Keep an original edge only when its ends sit in different components: 0 → 1. That contracted graph is a DAG. Topological sort orders it. This post stops at the DAG.

Java sketch

Adjacency list, a finish stack, an explicit transpose, a second DFS that writes component ids. Vertices that appear only as targets still need a key — same addVertex rule as the graph post.

static Map<String, Integer> kosaraju(Map<String, List<String>> g) {
    Set<String> verts = new LinkedHashSet<>(g.keySet());
    for (List<String> ns : g.values()) {
        verts.addAll(ns);
    }
    Set<String> seen = new HashSet<>();
    Deque<String> finish = new ArrayDeque<>();
    for (String u : verts) {
        dfsFinish(u, g, seen, finish);
    }
    Map<String, List<String>> gt = new HashMap<>();
    for (String v : verts) {
        gt.put(v, new ArrayList<>());
    }
    for (String u : g.keySet()) {
        for (String v : g.get(u)) {
            gt.get(v).add(u);
        }
    }
    seen.clear();
    Map<String, Integer> comp = new HashMap<>();
    int id = 0;
    while (!finish.isEmpty()) {
        String u = finish.pop();
        if (!seen.contains(u)) {
            dfsAssign(u, gt, seen, comp, id++);
        }
    }
    return comp;
}

static void dfsFinish(String u, Map<String, List<String>> g,
        Set<String> seen, Deque<String> finish) {
    if (!seen.add(u)) {
        return;
    }
    for (String v : g.getOrDefault(u, List.of())) {
        dfsFinish(v, g, seen, finish);
    }
    finish.push(u);
}

static void dfsAssign(String u, Map<String, List<String>> gt,
        Set<String> seen, Map<String, Integer> comp, int id) {
    if (!seen.add(u)) {
        return;
    }
    comp.put(u, id);
    for (String v : gt.getOrDefault(u, List.of())) {
        dfsAssign(v, gt, seen, comp, id);
    }
}

finish is an ArrayDeque used as a stack (push / pop). Do not use java.util.Stack — the DFS post already called that type a synchronized Vector. Production-sized first pass: the same deque with a leaving marker, not JVM frames.

Build the condensation by iterating original edges and adding comp[u] → comp[v] when the ids differ. Then order those supervertices with the topological-sort post.

Note: seen.clear() between passes is required. Reusing the first-pass set would skip the entire second forest.

Kosaraju is two walks plus a copy of the edge set. Tarjan finds the same partition in one DFS. It is a section, not a second post.

Stamp disc[u] on entry. Keep low[u]: the smallest discovery time reachable from u’s subtree that is still on the current path. Push u on that stack. A back edge to a vertex still on the stack can lower low; a tree-child returns its low. When you leave and low[u] == disc[u], pop until u — that pop is one SCC.

Same five vertices, start at A:

dfs(A) disc=0 low=0   stack [A]
  dfs(B) disc=1 low=1   stack [A, B]
    dfs(C) disc=2 low=2   stack [A, B, C]
      A on stack → low[C]=0
      dfs(D) disc=3 low=3   stack [A, B, C, D]
        dfs(E) disc=4 low=4
          D on stack → low[E]=3
        low[D]==disc[D] → pop E, D     SCC {D, E}
      low[C] stays 0
    low[B]=0
  low[A]==disc[A] → pop C, B, A        SCC {A, B, C}

An edge into an already-popped component must not update low (not on the stack). That is why the condensation stays a DAG. Recursion depth is still the longest path; the DFS post’s explicit stack applies. No second Java listing — implement Tarjan when you cannot afford the transpose, not because the name is fancier.

Complexity

Let V be vertices, E edges. Adjacency list; neighbor iteration is the hot path.

Kosaraju timeΘ(V + E): two forests plus a transpose
Tarjan timeΘ(V + E): one forest, constant work per edge
Extra RAMFinish / path stack, seen, component ids, plus G^T for Kosaraju
OutputA partition of V, then an optional condensation DAG of size ≤ V

You are iterating a layout, not ranking keys. A dense matrix makes each forest Θ(V²); that bill is the Graphs post. The RAM that surprises people is the call stack on a long path, or storing G and G^T when E is huge — Tarjan’s one walk is the answer to the second.

When not to compute SCCs

Skip this procedure when:

  • The graph is undirected. “Same component” is Union-Find or a walk. Strong connectivity is a directed question.
  • You only needed “is there a cycle?” Cycle Detection answers that with one walk. An SCC of size ≥ 2 implies a cycle; you do not need the full partition to fail a build.
  • The digraph is already a DAG. Every SCC is a singleton. Topological sort is the job; collapsing nothing is cargo-cult of the name.
  • A tool already clustered the call graph. Compilers and some static analyzers already emit SCCs. Pasting this sketch into a request path is the wrong system boundary.

Do not Union-Find a digraph by forgetting arrowheads. Do not DFS from one source and call the reachable set an SCC.

JDK: no Kosaraju class

There is no java.util.Kosaraju and no Tarjan. The library pieces are:

  • Layout: Map<K, List<K>> as in the graph post
  • Finish / path stack: Deque plus ArrayDeque (DFS)
  • seen and component ids: HashSet / HashMap (or int[] if vertices are 0 … n-1)

Prefer Kosaraju when you already have a DFS finish walk and can store the transpose. Prefer Tarjan when a second copy of E is the bill. Prefer Union-Find when the edges were never directed.

Do not use java.util.Stack. Do not Collections.reverse a finish list and skip the transpose.

Cheat sheet

Job:          partition a digraph into maximal mutually reachable sets
Strong:       u ⇝ v and v ⇝ u (not undirected "connected")
Kosaraju:     DFS finish stack, transpose, DFS in reverse finish order
Second tree:  one SCC
Transpose:    required; reverse-finish on G is not Kosaraju
Condensation: one vertex per SCC → a DAG → topological sort
Tarjan:       one DFS; low[u]==disc[u] pops a component (section, not a post)
Undirected:   Union-Find / a walk — different question
Time:         Θ(V + E)
JDK:          no Kosaraju type; Map+List, ArrayDeque, HashMap
Do not:       drop arrowheads; skip the forest; skip the transpose

Do:

  • Collect every vertex, including sinks, then forest both passes.
  • Flip the edges. Assign ids on the transpose in reverse finish order.
  • Contract to a DAG, then take that DAG to topological sort.

Don’t:

  • Union-Find a directed call graph and call the blob strongly connected.
  • DFS only from a source and name the reachable set an SCC.
  • Reverse-finish the original graph and skip the transpose.
  • Ship java.util.Stack, or a second full Tarjan listing because the name showed up.

Wrap-up

Strong connectivity is mutual reachability on a digraph. Kosaraju records DFS finish order, transposes the edges, and DFS-walks again in reverse finish order; each second-pass tree is an SCC. The condensation — one vertex per component — is a DAG, and topological sort is the next procedure, not a second SCC algorithm. Tarjan does the same partition in one walk with lowlink when you cannot store G^T. Union-Find answers the undirected question. The JDK gives you ArrayDeque and a map, not a clustering API. Hand-roll the sketch when the digraph is the assignment.

The catalog continues with string matching. Next is KMP: linear scan, no retreat on the haystack.

Next optional step in the series Find a pattern without sliding back on the text. KMP: Find a Pattern Without Sliding Back on the Text