34.06Intermediate / Advanced3 topics15 min3 interactive animations

Strongly connected components intro

A strongly connected component is a maximal set of vertices that all reach each other; shrinking each component to one vertex gives the condensation graph, which is always a DAG.

Learning goals

Define strongly connected components and test whether two vertices share one
Find components with Kosaraju's two-pass algorithm
Build the condensation graph
Explain why the condensation has no cycle

Prerequisites

Directed reachabilityDepth-first search

Many directed graphs are tangled: groups of vertices that all depend on each other, linked by one-way arrows. Collapsing each tangle to a single vertex leaves a clean DAG that the algorithms of this chapter can handle.

34.06.1

SCC definition

Two vertices a and b are **strongly connected** when there is a path from a to b *and* a path from b to a. This is an equivalence relation, so the vertices split into disjoint **strongly connected components** (SCCs). A vertex that lies on no cycle is a component by itself.

The direct test for one pair is two searches. To find all components at once use a linear-time method such as Kosaraju's, which the animation runs: one DFS records finish order, a second DFS on the reversed graph labels components.

Java

1static boolean inSameScc(List<List<Integer>> g, int a, int b) {   // a reaches b and b reaches a
2    return reaches(g, a, b) && reaches(g, b, a);
3}
4static boolean reaches(List<List<Integer>> g, int s, int t) {
5    boolean[] seen = new boolean[g.size()];
6    Deque<Integer> stack = new ArrayDeque<>();
7    seen[s] = true;
8    stack.push(s);
9    while (!stack.isEmpty()) {
10        int u = stack.pop();
11        if (u == t) return true;
12        for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }
13    }
14    return false;
15}

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.

34.06.2

Condensation graph

The **condensation graph** has one vertex per component and an arrow from component A to component B when some arrow of the original goes from a vertex of A to a vertex of B. Arrows inside a component disappear, and duplicate arrows between the same pair are kept only once.

Kosaraju's algorithm labels components in a convenient order: component 0 is a source of the condensation, and every arrow between components goes from a smaller number to a larger one. The animation prints the condensation's arrows after the labelling.

Java

1static class Condensation {
2    final int[] comp;                                        // comp[v] = id of v's component, in topological order of the condensation
3    final int count;
4    final List<Set<Integer>> arrows = new ArrayList<>();     // arrows.get(c) = components that c points to
5    Condensation(List<List<Integer>> g) {
6        int n = g.size();
7        Deque<Integer> order = new ArrayDeque<>();
8        boolean[] seen = new boolean[n];
9        for (int s = 0; s < n; s++) if (!seen[s]) pass1(g, s, seen, order);
10        List<List<Integer>> rev = new ArrayList<>();
11        for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
12        for (int u = 0; u < n; u++) for (int v : g.get(u)) rev.get(v).add(u);
13        comp = new int[n];
14        Arrays.fill(comp, -1);
15        int c = 0;
16        for (int s : order) if (comp[s] == -1) pass2(rev, s, c++);
17        count = c;
18        for (int i = 0; i < count; i++) arrows.add(new TreeSet<>());
19        for (int u = 0; u < n; u++) for (int v : g.get(u)) if (comp[u] != comp[v]) arrows.get(comp[u]).add(comp[v]);
20    }
21    private void pass1(List<List<Integer>> g, int u, boolean[] seen, Deque<Integer> order) {
22        seen[u] = true;
23        for (int v : g.get(u)) if (!seen[v]) pass1(g, v, seen, order);
24        order.addFirst(u);                                   // latest finisher first
25    }
26    private void pass2(List<List<Integer>> rev, int u, int id) {
27        comp[u] = id;
28        for (int v : rev.get(u)) if (comp[v] == -1) pass2(rev, v, id);
29    }
30}

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.

34.06.3

Why condensation is a DAG

Suppose the condensation had a cycle A → B → ... → A. Then every vertex of A could reach every vertex of B and back, so all of them would be mutually reachable and belong to one component, contradicting that A and B are different components. So the condensation has no cycle: it is always a DAG.

This is why SCCs turn any directed graph into a DAG problem: collapse the tangles, then use topological order, DAG dynamic programming or reachability on the components. The check below confirms that no arrow between components goes from a larger label to a smaller one.

Java

1static boolean componentsAreTopological(List<List<Integer>> g, int[] comp) {   // comp from Kosaraju as above
2    for (int u = 0; u < g.size(); u++)
3        for (int v : g.get(u))
4            if (comp[u] > comp[v]) return false;      // an arrow against the order would be a cycle between components
5    return true;
6}

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

Medium

Find Eventual Safe States
Course Schedule

Advanced

Maximum Employees to Be Invited to a Meeting

Key takeaways

Strongly connected means mutually reachable; the relation splits vertices into disjoint components.
Kosaraju: DFS for finish order, then DFS on the reversed graph in decreasing finish order.
The condensation has one vertex per component and is always a DAG.
Collapse each component, then apply topological methods to the condensation.