38.04Intermediate / Advanced4 topics17 min4 interactive animations

Strongly connected components

In a directed graph a strongly connected component is a maximal set of vertices that can all reach each other. Kosaraju's two passes and Tarjan's single pass both find them in linear time, and contracting them leaves a DAG.

Learning goals

Run Kosaraju's algorithm: finishing order, reversed graph, second pass
Run Tarjan's algorithm with low-link and a stack
Build the condensation DAG
State which component numbering is topological for each algorithm

Prerequisites

DFS timestamps and low-linkDirected graphs and DAGs (Chapter 34)

In a city of one-way streets, a strongly connected component is a neighbourhood where you can get from any junction to any other. Between neighbourhoods traffic only flows one way, so the neighbourhoods themselves form a DAG.

38.04.1

Kosaraju

Two vertices are in the same **strongly connected component** (SCC) when each can reach the other. SCCs partition the vertices.

**Kosaraju** uses two DFS passes. Pass 1: run DFS on the graph and push each vertex on a stack when it **finishes**. Pass 2: take vertices from the stack top (latest finish first) and run DFS on the **reversed** graph; every tree the second pass grows is one SCC.

Why it works: the vertex that finishes last in pass 1 lies in a source component of the condensation. In the reversed graph that component can reach nothing outside itself, so the DFS stays inside it. Remove it, and the next latest finisher is in a source of what remains. Run the “Three cycles joined by one-way arrows” preset (Chapter 34's scc-kosaraju animation) and watch the first pass produce the order, then the second pass paint one colour per component.

With this numbering the components come out in **topological order** of the condensation: component 0 is a source, and every arrow between components goes from a smaller to a larger number. Time O(n + m), with two traversals and one reversed copy of the graph.

Java

1static int[] kosaraju(int n, int[][] edges) {          // comp[v], numbered in topological order of the condensation
2    List<Integer>[] g = adjacency(n, edges, false), rev = adjacency(n, edges, true);
3    boolean[] seen = new boolean[n];
4    Deque<Integer> order = new ArrayDeque<>();           // last finished vertex on top
5    for (int v = 0; v < n; v++) if (!seen[v]) finishOrder(g, v, seen, order);
6    int[] comp = new int[n];
7    Arrays.fill(comp, -1);
8    int count = 0;
9    while (!order.isEmpty()) {
10        int v = order.pop();
11        if (comp[v] == -1) paint(rev, v, comp, count++);
12    }
13    return comp;
14}
15
16@SuppressWarnings("unchecked")
17static List<Integer>[] adjacency(int n, int[][] edges, boolean reversed) {
18    List<Integer>[] g = new List[n];
19    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
20    for (int[] e : edges) g[reversed ? e[1] : e[0]].add(reversed ? e[0] : e[1]);
21    return g;
22}
23
24static void finishOrder(List<Integer>[] g, int u, boolean[] seen, Deque<Integer> order) {
25    seen[u] = true;
26    for (int v : g[u]) if (!seen[v]) finishOrder(g, v, seen, order);
27    order.push(u);                                       // u finishes now
28}
29
30static void paint(List<Integer>[] rev, int u, int[] comp, int c) {
31    comp[u] = c;
32    for (int v : rev[u]) if (comp[v] == -1) paint(rev, v, comp, c);
33}

Worst

O(n + m)

Space

O(n + m)

Strongly connected components and the condensation graph (Kosaraju)

Interactive · edit the input

pass 1: DFS on the graph · 8 vertices · 10 edges

Being processedComponent 1Component 2Component 3Component 4Component 5 and up

finish order (latest first)

none yet

component of v

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Two vertices are in the same strongly connected component when each can reach the other. Kosaraju finds them with two DFS passes: first record finish times on the graph, then search the reversed graph starting from the latest finisher.

Step 1 / 21

Java

1int[] kosaraju(List<List<Integer>> g) {          // comp[v] = id of v's strongly connected component
2    int n = g.size();
3    Deque<Integer> order = new ArrayDeque<>();
4    boolean[] seen = new boolean[n];
5    for (int s = 0; s < n; s++) if (!seen[s]) finishOrder(g, s, seen, order);   // pass 1: DFS on g
6    List<List<Integer>> rev = new ArrayList<>();
7    for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
8    for (int u = 0; u < n; u++) for (int v : g.get(u)) rev.get(v).add(u);
9    int[] comp = new int[n]; Arrays.fill(comp, -1);
10    int count = 0;
11    for (int s : order)                          // latest finisher first
12        if (comp[s] == -1) label(rev, s, comp, count++);   // pass 2: DFS on the reversed graph
13    return comp;
14}
15void finishOrder(List<List<Integer>> g, int u, boolean[] seen, Deque<Integer> order) {
16    seen[u] = true;
17    for (int v : g.get(u)) if (!seen[v]) finishOrder(g, v, seen, order);
18    order.addFirst(u);                           // finished
19}
20void label(List<List<Integer>> rev, int u, int[] comp, int id) {
21    comp[u] = id;
22    for (int v : rev.get(u)) if (comp[v] == -1) label(rev, v, comp, id);
23}

Live state

0 vertices finished0 components

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L2	n=8	Two vertices are in the same strongly connected component when each can reach the other. Kosaraju finds them with two DFS passes: first record finish times on the graph, then search the reversed graph starting from the latest finisher.
2	L15	u=5 finished=[5]	Pass 1: 5 finishes. Finish order so far: [5].
3	L15	u=4 finished=[5, 4]	Pass 1: 4 finishes. Finish order so far: [5, 4].
4	L15	u=3 finished=[5, 4, 3]	Pass 1: 3 finishes. Finish order so far: [5, 4, 3].
5	L15	u=2 finished=[5, 4, 3, 2]	Pass 1: 2 finishes. Finish order so far: [5, 4, 3, 2].
6	L15	u=1 finished=[5, 4, 3, 2, 1]	Pass 1: 1 finishes. Finish order so far: [5, 4, 3, 2, 1].
7	L15	u=0 finished=[5, 4, 3, 2, 1, 0]	Pass 1: 0 finishes. Finish order so far: [5, 4, 3, 2, 1, 0].
8	L15	u=7 finished=[5, 4, 3, 2, 1, 0, 7]	Pass 1: 7 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7].
9	L15	u=6 finished=[5, 4, 3, 2, 1, 0, 7, 6]	Pass 1: 6 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7, 6].
10	L10	s=6 component=0	6 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 6 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
11	L18	u=6 component=0	Pass 2: 6 joins component 0.
12	L18	u=7 component=0	Pass 2: 7 joins component 0.
13	L10	s=0 component=1	0 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 0 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
14	L18	u=0 component=1	Pass 2: 0 joins component 1.
15	L18	u=2 component=1	Pass 2: 2 joins component 1.
16	L18	u=1 component=1	Pass 2: 1 joins component 1.
17	L10	s=3 component=2	3 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 3 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
18	L18	u=3 component=2	Pass 2: 3 joins component 2.
19	L18	u=5 component=2	Pass 2: 5 joins component 2.
20	L18	u=4 component=2	Pass 2: 4 joins component 2.
21	L12	return={0,1,2} {3,4,5} {6,7} components=3	3 strongly connected components: {0, 1, 2} {3, 4, 5} {6, 7}. Condensation (one vertex per component) has 2 arrows: C1→C2, C0→C2. It can never contain a cycle: two components on a cycle would be one component.

38.04.2

Tarjan SCC

**Tarjan's algorithm** finds the SCCs in a single DFS using the same tin/low idea as bridges. Push each vertex on a stack when entered and keep a flag onStack. For an arrow u → v: if v is new, recurse and take low[u] = min(low[u], low[v]); if v is already on the stack, it is in the same SCC-in-progress, so low[u] = min(low[u], tin[v]); if v is finished and off the stack, it belongs to a completed component, and the arrow is ignored.

When low[u] == tin[u], u is the root of an SCC: nothing in its subtree reaches anything older that is still open. Pop the stack down to u; the popped vertices are one component.

Components are numbered in the order they finish, which is **reverse topological order**: the first component popped is a sink (nothing leaves it), and every arrow between components goes from a larger number to a smaller one. That is the opposite of Kosaraju's numbering. The method returns a comp array and works one DFS tree at a time, so it handles disconnected graphs without extra code.

Java

1static class Tarjan {
2    int timer = 0, count = 0;
3    int[] tin, low, comp;
4    boolean[] onStack;
5    Deque<Integer> stack = new ArrayDeque<>();
6
7    int[] run(List<Integer>[] g) {                       // comp[v], numbered in reverse topological order (0 = a sink)
8        int n = g.length;
9        tin = new int[n]; low = new int[n]; comp = new int[n]; onStack = new boolean[n];
10        for (int v = 0; v < n; v++) if (tin[v] == 0) dfs(g, v);
11        return comp;
12    }
13
14    void dfs(List<Integer>[] g, int u) {
15        tin[u] = low[u] = ++timer;
16        stack.push(u); onStack[u] = true;
17        for (int v : g[u]) {
18            if (tin[v] == 0) {
19                dfs(g, v);
20                low[u] = Math.min(low[u], low[v]);
21            } else if (onStack[v]) {
22                low[u] = Math.min(low[u], tin[v]);       // v is in the component being built
23            }
24        }
25        if (low[u] == tin[u]) {                          // u is the root of a component
26            int x;
27            do { x = stack.pop(); onStack[x] = false; comp[x] = count; } while (x != u);
28            count++;
29        }
30    }
31}
32
33static int[] tarjanScc(List<Integer>[] g) {
34    return new Tarjan().run(g);
35}

Worst

O(n + m)

Space

O(n)

Strongly connected components and the condensation graph (Kosaraju)

Interactive · edit the input

pass 1: DFS on the graph · 8 vertices · 10 edges

Being processedComponent 1Component 2Component 3Component 4Component 5 and up

finish order (latest first)

none yet

component of v

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Step 1 / 21

Java

1int[] kosaraju(List<List<Integer>> g) {          // comp[v] = id of v's strongly connected component
2    int n = g.size();
3    Deque<Integer> order = new ArrayDeque<>();
4    boolean[] seen = new boolean[n];
5    for (int s = 0; s < n; s++) if (!seen[s]) finishOrder(g, s, seen, order);   // pass 1: DFS on g
6    List<List<Integer>> rev = new ArrayList<>();
7    for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
8    for (int u = 0; u < n; u++) for (int v : g.get(u)) rev.get(v).add(u);
9    int[] comp = new int[n]; Arrays.fill(comp, -1);
10    int count = 0;
11    for (int s : order)                          // latest finisher first
12        if (comp[s] == -1) label(rev, s, comp, count++);   // pass 2: DFS on the reversed graph
13    return comp;
14}
15void finishOrder(List<List<Integer>> g, int u, boolean[] seen, Deque<Integer> order) {
16    seen[u] = true;
17    for (int v : g.get(u)) if (!seen[v]) finishOrder(g, v, seen, order);
18    order.addFirst(u);                           // finished
19}
20void label(List<List<Integer>> rev, int u, int[] comp, int id) {
21    comp[u] = id;
22    for (int v : rev.get(u)) if (comp[v] == -1) label(rev, v, comp, id);
23}

Live state

0 vertices finished0 components

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L2	n=8	Two vertices are in the same strongly connected component when each can reach the other. Kosaraju finds them with two DFS passes: first record finish times on the graph, then search the reversed graph starting from the latest finisher.
2	L15	u=5 finished=[5]	Pass 1: 5 finishes. Finish order so far: [5].
3	L15	u=4 finished=[5, 4]	Pass 1: 4 finishes. Finish order so far: [5, 4].
4	L15	u=3 finished=[5, 4, 3]	Pass 1: 3 finishes. Finish order so far: [5, 4, 3].
5	L15	u=2 finished=[5, 4, 3, 2]	Pass 1: 2 finishes. Finish order so far: [5, 4, 3, 2].
6	L15	u=1 finished=[5, 4, 3, 2, 1]	Pass 1: 1 finishes. Finish order so far: [5, 4, 3, 2, 1].
7	L15	u=0 finished=[5, 4, 3, 2, 1, 0]	Pass 1: 0 finishes. Finish order so far: [5, 4, 3, 2, 1, 0].
8	L15	u=7 finished=[5, 4, 3, 2, 1, 0, 7]	Pass 1: 7 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7].
9	L15	u=6 finished=[5, 4, 3, 2, 1, 0, 7, 6]	Pass 1: 6 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7, 6].
10	L10	s=6 component=0	6 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 6 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
11	L18	u=6 component=0	Pass 2: 6 joins component 0.
12	L18	u=7 component=0	Pass 2: 7 joins component 0.
13	L10	s=0 component=1	0 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 0 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
14	L18	u=0 component=1	Pass 2: 0 joins component 1.
15	L18	u=2 component=1	Pass 2: 2 joins component 1.
16	L18	u=1 component=1	Pass 2: 1 joins component 1.
17	L10	s=3 component=2	3 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 3 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
18	L18	u=3 component=2	Pass 2: 3 joins component 2.
19	L18	u=5 component=2	Pass 2: 5 joins component 2.
20	L18	u=4 component=2	Pass 2: 4 joins component 2.
21	L12	return={0,1,2} {3,4,5} {6,7} components=3	3 strongly connected components: {0, 1, 2} {3, 4, 5} {6, 7}. Condensation (one vertex per component) has 2 arrows: C1→C2, C0→C2. It can never contain a cycle: two components on a cycle would be one component.

38.04.3

SCC condensation DAG

Replace every SCC by one vertex and keep one arrow between two components whenever any arrow in the original joins them. The result is the **condensation**, and it is always a DAG: a cycle among components would let their vertices reach each other, merging them into one component.

The condensation turns hard questions into DAG questions. Reachability, longest paths and counting paths (Chapter 37) become dynamic programming over the components. The “Three cycles joined by one-way arrows” preset condenses 8 vertices to 3 components, and the “A DAG: every vertex is alone” preset condenses to itself, because a DAG has no cycles to collapse.

Remove duplicate arrows between the same pair of components; otherwise path counts are inflated. The code below keeps each pair once with a HashSet of encoded pairs.

Java

1static List<int[]> condensation(int[][] edges, int[] comp) {   // distinct arrows {a, b} between different components
2    Set<Long> seen = new HashSet<>();
3    List<int[]> dag = new ArrayList<>();
4    for (int[] e : edges) {
5        int a = comp[e[0]], b = comp[e[1]];
6        if (a != b && seen.add((long) a * 1_000_000 + b)) dag.add(new int[]{a, b});
7    }
8    return dag;
9}

Strongly connected components and the condensation graph (Kosaraju)

Interactive · edit the input

pass 1: DFS on the graph · 8 vertices · 10 edges

Being processedComponent 1Component 2Component 3Component 4Component 5 and up

finish order (latest first)

none yet

component of v

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Step 1 / 21

Java

1int[] kosaraju(List<List<Integer>> g) {          // comp[v] = id of v's strongly connected component
2    int n = g.size();
3    Deque<Integer> order = new ArrayDeque<>();
4    boolean[] seen = new boolean[n];
5    for (int s = 0; s < n; s++) if (!seen[s]) finishOrder(g, s, seen, order);   // pass 1: DFS on g
6    List<List<Integer>> rev = new ArrayList<>();
7    for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
8    for (int u = 0; u < n; u++) for (int v : g.get(u)) rev.get(v).add(u);
9    int[] comp = new int[n]; Arrays.fill(comp, -1);
10    int count = 0;
11    for (int s : order)                          // latest finisher first
12        if (comp[s] == -1) label(rev, s, comp, count++);   // pass 2: DFS on the reversed graph
13    return comp;
14}
15void finishOrder(List<List<Integer>> g, int u, boolean[] seen, Deque<Integer> order) {
16    seen[u] = true;
17    for (int v : g.get(u)) if (!seen[v]) finishOrder(g, v, seen, order);
18    order.addFirst(u);                           // finished
19}
20void label(List<List<Integer>> rev, int u, int[] comp, int id) {
21    comp[u] = id;
22    for (int v : rev.get(u)) if (comp[v] == -1) label(rev, v, comp, id);
23}

Live state

0 vertices finished0 components

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L2	n=8	Two vertices are in the same strongly connected component when each can reach the other. Kosaraju finds them with two DFS passes: first record finish times on the graph, then search the reversed graph starting from the latest finisher.
2	L15	u=5 finished=[5]	Pass 1: 5 finishes. Finish order so far: [5].
3	L15	u=4 finished=[5, 4]	Pass 1: 4 finishes. Finish order so far: [5, 4].
4	L15	u=3 finished=[5, 4, 3]	Pass 1: 3 finishes. Finish order so far: [5, 4, 3].
5	L15	u=2 finished=[5, 4, 3, 2]	Pass 1: 2 finishes. Finish order so far: [5, 4, 3, 2].
6	L15	u=1 finished=[5, 4, 3, 2, 1]	Pass 1: 1 finishes. Finish order so far: [5, 4, 3, 2, 1].
7	L15	u=0 finished=[5, 4, 3, 2, 1, 0]	Pass 1: 0 finishes. Finish order so far: [5, 4, 3, 2, 1, 0].
8	L15	u=7 finished=[5, 4, 3, 2, 1, 0, 7]	Pass 1: 7 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7].
9	L15	u=6 finished=[5, 4, 3, 2, 1, 0, 7, 6]	Pass 1: 6 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7, 6].
10	L10	s=6 component=0	6 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 6 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
11	L18	u=6 component=0	Pass 2: 6 joins component 0.
12	L18	u=7 component=0	Pass 2: 7 joins component 0.
13	L10	s=0 component=1	0 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 0 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
14	L18	u=0 component=1	Pass 2: 0 joins component 1.
15	L18	u=2 component=1	Pass 2: 2 joins component 1.
16	L18	u=1 component=1	Pass 2: 1 joins component 1.
17	L10	s=3 component=2	3 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 3 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
18	L18	u=3 component=2	Pass 2: 3 joins component 2.
19	L18	u=5 component=2	Pass 2: 5 joins component 2.
20	L18	u=4 component=2	Pass 2: 4 joins component 2.
21	L12	return={0,1,2} {3,4,5} {6,7} components=3	3 strongly connected components: {0, 1, 2} {3, 4, 5} {6, 7}. Condensation (one vertex per component) has 2 arrows: C1→C2, C0→C2. It can never contain a cycle: two components on a cycle would be one component.

38.04.4

Component ordering

Both algorithms give components a topological structure for free; what differs is the direction. **Kosaraju**: component 0 is a source; every condensation arrow goes from a smaller number to a larger. **Tarjan**: component 0 is a sink; every arrow goes from a larger number to a smaller.

A processing order that respects the arrows is what DAG dynamic programming needs. With Tarjan's numbering loop c = 0, 1, 2, ... and each component only needs values from components already finished; with Kosaraju's, loop downwards. Renumbering Tarjan's result with count - 1 - comp gives Kosaraju-style topological numbers.

Do not assume the numbering is unique: several topological orders may exist when components are not comparable, and different DFS start orders give different (all valid) numberings.

Java

1static int[] topologicalNumbers(int[] tarjanComp, int count) {   // reverse Tarjan's numbering: arrows then go from small to large
2    int[] out = new int[tarjanComp.length];
3    for (int v = 0; v < tarjanComp.length; v++) out[v] = count - 1 - tarjanComp[v];
4    return out;
5}

Strongly connected components and the condensation graph (Kosaraju)

Interactive · edit the input

pass 1: DFS on the graph · 8 vertices · 10 edges

Being processedComponent 1Component 2Component 3Component 4Component 5 and up

finish order (latest first)

none yet

component of v

-0

-1

-2

-3

-4

-5

-6

-7

Setup

Step 1 / 21

Java

1int[] kosaraju(List<List<Integer>> g) {          // comp[v] = id of v's strongly connected component
2    int n = g.size();
3    Deque<Integer> order = new ArrayDeque<>();
4    boolean[] seen = new boolean[n];
5    for (int s = 0; s < n; s++) if (!seen[s]) finishOrder(g, s, seen, order);   // pass 1: DFS on g
6    List<List<Integer>> rev = new ArrayList<>();
7    for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
8    for (int u = 0; u < n; u++) for (int v : g.get(u)) rev.get(v).add(u);
9    int[] comp = new int[n]; Arrays.fill(comp, -1);
10    int count = 0;
11    for (int s : order)                          // latest finisher first
12        if (comp[s] == -1) label(rev, s, comp, count++);   // pass 2: DFS on the reversed graph
13    return comp;
14}
15void finishOrder(List<List<Integer>> g, int u, boolean[] seen, Deque<Integer> order) {
16    seen[u] = true;
17    for (int v : g.get(u)) if (!seen[v]) finishOrder(g, v, seen, order);
18    order.addFirst(u);                           // finished
19}
20void label(List<List<Integer>> rev, int u, int[] comp, int id) {
21    comp[u] = id;
22    for (int v : rev.get(u)) if (comp[v] == -1) label(rev, v, comp, id);
23}

Live state

0 vertices finished0 components

No condition evaluated on this step

Execution trace (dry run table)Show 21 steps

Step	Line	State	What happens
1	L2	n=8	Two vertices are in the same strongly connected component when each can reach the other. Kosaraju finds them with two DFS passes: first record finish times on the graph, then search the reversed graph starting from the latest finisher.
2	L15	u=5 finished=[5]	Pass 1: 5 finishes. Finish order so far: [5].
3	L15	u=4 finished=[5, 4]	Pass 1: 4 finishes. Finish order so far: [5, 4].
4	L15	u=3 finished=[5, 4, 3]	Pass 1: 3 finishes. Finish order so far: [5, 4, 3].
5	L15	u=2 finished=[5, 4, 3, 2]	Pass 1: 2 finishes. Finish order so far: [5, 4, 3, 2].
6	L15	u=1 finished=[5, 4, 3, 2, 1]	Pass 1: 1 finishes. Finish order so far: [5, 4, 3, 2, 1].
7	L15	u=0 finished=[5, 4, 3, 2, 1, 0]	Pass 1: 0 finishes. Finish order so far: [5, 4, 3, 2, 1, 0].
8	L15	u=7 finished=[5, 4, 3, 2, 1, 0, 7]	Pass 1: 7 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7].
9	L15	u=6 finished=[5, 4, 3, 2, 1, 0, 7, 6]	Pass 1: 6 finishes. Finish order so far: [5, 4, 3, 2, 1, 0, 7, 6].
10	L10	s=6 component=0	6 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 6 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
11	L18	u=6 component=0	Pass 2: 6 joins component 0.
12	L18	u=7 component=0	Pass 2: 7 joins component 0.
13	L10	s=0 component=1	0 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 0 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
14	L18	u=0 component=1	Pass 2: 0 joins component 1.
15	L18	u=2 component=1	Pass 2: 2 joins component 1.
16	L18	u=1 component=1	Pass 2: 1 joins component 1.
17	L10	s=3 component=2	3 is the latest finisher not yet labelled: search the reversed graph from it. The search can only reach vertices that reach 3 in the original graph, and none of them can lie in a later-finishing component, so it stays inside one component.
18	L18	u=3 component=2	Pass 2: 3 joins component 2.
19	L18	u=5 component=2	Pass 2: 5 joins component 2.
20	L18	u=4 component=2	Pass 2: 4 joins component 2.
21	L12	return={0,1,2} {3,4,5} {6,7} components=3	3 strongly connected components: {0, 1, 2} {3, 4, 5} {6, 7}. Condensation (one vertex per component) has 2 arrows: C1→C2, C0→C2. It can never contain a cycle: two components on a cycle would be one component.

Practice ladder

Now try it yourself

Easy

Find the Town Judge
Minimum Number of Vertices to Reach All Nodes

Medium

Course Schedule
Find Eventual Safe States
Number of Provinces

Advanced

Maximum Employees to Be Invited to a Meeting
Critical Connections in a Network

Key takeaways

Kosaraju: DFS for finishing order, then DFS on the reversed graph in that order; components come out source-first.
Tarjan: one DFS with a stack; pop a component when low[u] == tin[u]; components come out sink-first.
The condensation of any directed graph is a DAG.