Strongly connected components

A strongly connected component of a directed graph is a largest set of vertices in which every vertex can reach every other one. Shrinking each component to one vertex turns any directed graph into a graph without cycles, so problems about reachability or paths in graphs with cycles become topological sort or DP problems. Kosaraju's algorithm finds the components with two DFS passes in O(n + m). With two-way edges, plain connected components are enough.

Explanation

This graph has 8 vertices and 10 one-way edges.

Fig. 1. Which vertices are in the same component as vertex 1?

Two vertices are in the same strongly connected component when each can reach the other. Every vertex is in exactly one component, and a vertex on no cycle is a component of its own.

The connected components loop would start a search at vertex 1 and take every vertex it reaches. Here the search reaches 1, 2, 3 and 4. But vertex 4 has no outgoing edge, so 4 can't reach 1. The loop's next search, from 5, collects vertex 8 the same way.

Fig. 2. The red edge leads out of the blue cycle, and no edge comes back.

A search collects vertices outside its component only when an edge leads out of the component to a vertex that isn't in a component yet. Vertex 4 is in a component that no edge leaves, a sink, so a search started there collects only 4. Once 4 is in a component, a search from 1 collects exactly 1, 2 and 3: its only edge out of the cycle leads to 4, which is already in a component. Then a search from 8 collects only 8, and one from 5 collects 5, 6 and 7. So the order of the starts matters. Always start in a component whose edges lead out only to components already collected. We need this order before we know the components.

Run the DFS of topological sort on the whole graph, with the outer loop over all vertices, and keep its finish order.

The finish order is 4, 3, 2, 1, 7, 8, 6, 5. Topological sort reads it from the end. We want sinks first, so try reading it from the front and searching forwards. Vertex 4, finished first, is in a sink, and its search collects only 4. Next comes 3, and its search collects 1, 2 and 3. Then comes 7, and its search goes on to 5, 6 and 8, so 8 lands in the component of 7. Vertex 7 finished before 8, although its component has an edge to 8. The vertex finished first doesn't even have to be in a sink: with edges 1 \to 2, 2 \to 1 and 1 \to 3, the DFS from 1 finishes 2 first, and the component of 1 and 2 has an edge to 3.

The other end of the order can be trusted. The outer loop's last search finishes its start last, so the latest finished vertex is where the last search started. A vertex from which this start can be reached was not visited by an earlier search, because that search would have reached the start too. It was visited in the last search, so the start reaches it, and the two are in one component. No edge enters this component from outside. That is the opposite of a sink.

Reverse every edge. A cycle reversed is still a cycle, so the components stay the same, but now no edge leaves the component of the latest finished vertex. A search from it along the reversed edges collects its component and nothing else. Then take the latest finished vertex not in a component yet, and search again. This method is Kosaraju's algorithm.

Here are both passes on the example.

The first pass starts a search at vertex 1, the first vertex not visited yet.

The search follows the edge from 1 to 2 and visits vertex 2.

The search follows the edge from 2 to 3 and visits vertex 3.

The search follows the edge from 3 to 4 and visits vertex 4.

Every edge out of vertex 4 is checked, so 4 is finished and goes to the end of the finish order.

Every edge out of vertex 3 is checked, so 3 is finished and goes to the end of the finish order.

Every edge out of vertex 2 is checked, so 2 is finished and goes to the end of the finish order.

Every edge out of vertex 1 is checked, so 1 is finished and goes to the end of the finish order.

The first pass starts a search at vertex 5, the first vertex not visited yet.

The search follows the edge from 5 to 6 and visits vertex 6.

The search follows the edge from 6 to 7 and visits vertex 7.

Every edge out of vertex 7 is checked, so 7 is finished and goes to the end of the finish order.

The search follows the edge from 6 to 8 and visits vertex 8.

Every edge out of vertex 8 is checked, so 8 is finished and goes to the end of the finish order.

Every edge out of vertex 6 is checked, so 6 is finished and goes to the end of the finish order.

Every edge out of vertex 5 is checked, so 5 is finished and goes to the end of the finish order.

Every edge is reversed. The second pass reads the finish order from the end, starting with vertex 5.

Vertex 5 is the latest finished vertex not in a component yet, so a search along the reversed edges starts there, and 5 gets component 1.

The reversed edge from 5 to 7 leads to vertex 7, which joins component 1.

The reversed edge from 7 to 6 leads to vertex 6, which joins component 1.

Vertex 8 is the latest finished vertex not in a component yet, so a search along the reversed edges starts there, and 8 gets component 2.

The reversed edge from 8 to 6 leads into component 1, collected earlier, so the search doesn't go there.

Vertex 1 is the latest finished vertex not in a component yet, so a search along the reversed edges starts there, and 1 gets component 3.

The reversed edge from 1 to 3 leads to vertex 3, which joins component 3.

The reversed edge from 3 to 2 leads to vertex 2, which joins component 3.

The reversed edge from 2 to 7 leads into component 1, collected earlier, so the search doesn't go there.

Vertex 4 is the latest finished vertex not in a component yet, so a search along the reversed edges starts there, and 4 gets component 4.

The reversed edge from 4 to 3 leads into component 3, collected earlier, so the search doesn't go there.

The reversed edge from 4 to 8 leads into component 2, collected earlier, so the search doesn't go there.

Every vertex is in a component: 5, 6 and 7 in component 1, 8 in component 2, 1, 2 and 3 in component 3, and 4 in component 4.

1/30

Fig. 4. Step through both passes with the buttons. In the first pass, light blue vertices are on the current route, green ones are finished, and the boxes below hold the finish order. In the second pass the boxes hold the finish order from the end, crossed out once a vertex is in a component, and each component gets its own colour. A grey arrow is a reversed edge into an earlier component, where the search stops.

The second pass starts its searches at 5, 8, 1 and 4 and finds 4 components: 5, 6 and 7, then 8, then 1, 2 and 3, then 4. Each search stops at the reversed edges into components collected earlier.

The condensation

Shrink each component to one vertex and keep the edges between components. This graph is the condensation; for the example it has 4 edges. It has no cycle: a cycle through two components would let each reach the other, so they would be one component. It can be sorted topologically, and Kosaraju's algorithm already finds the components in that order.

Fig. 5. Each component is one vertex. All 4 edges between components go left to right.

To reach every vertex starting from as few vertices as possible, start once in every component that no edge enters; here one start, in the component of 5, 6 and 7, is enough. To find the most distinct vertices one path can visit, give each vertex of the condensation the size of its component and find the heaviest path in topological order.

Implementation

The graph has n vertices and m edges and is stored as an adjacency list adj. The reversed graph radj is built while reading: an edge from a to b adds b to adj[a] and a to radj[b]. The second pass writes the component number of v into comp[v]; comp[v] == 0 means that v is not in a component yet.

1. First pass: run dfs1 on adj from every unvisited vertex, in an outer loop; append each vertex to order when it is finished, that is, when its call returns.

2. Second pass: go through order from the end; every vertex v with comp[v] == 0 starts dfs2(v, ++c) on radj, which gives every vertex it reaches the number c. On the example order is 4 3 2 1 7 8 6 5, so the searches start at 5, 8, 1 and 4 and get c = 1, 2, 3, 4.

The program reads n and m, then m lines a b, an edge from a to b, with vertices numbered from 1. It prints the number of components and then the component of each vertex. Then it builds the condensation and prints the components that no edge enters. For the example the input is:

8 10
1 2
2 3
3 1
3 4
5 6
6 7
6 8
7 2
7 5
8 4

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int n, m;
vector<vector<int>> adj, radj;
vector<bool> visited;
vector<int> order, comp;

// first pass
void dfs1(int v) {
    visited[v] = true;
    for (int u : adj[v])
        if (!visited[u]) dfs1(u);
    order.push_back(v);                 // v is finished
}

// second pass
void dfs2(int v, int c) {
    comp[v] = c;
    for (int u : radj[v])
        if (comp[u] == 0) dfs2(u, c);
}

int main() {
    cin >> n >> m;
    adj.assign(n + 1, {});
    radj.assign(n + 1, {});
    vector<pair<int, int>> edges;       // only needed for the condensation
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        radj[b].push_back(a);           // reverse the edges
        edges.push_back({a, b});        // only needed for the condensation
    }

    // first pass
    visited.assign(n + 1, false);
    for (int v = 1; v <= n; v++)
        if (!visited[v]) dfs1(v);

    // second pass
    comp.assign(n + 1, 0);
    int c = 0;
    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];
        if (comp[v] == 0) dfs2(v, ++c);
    }

    // answer
    cout << c << "\n";
    for (int v = 1; v <= n; v++)
        cout << comp[v] << (v < n ? ' ' : '\n');

    // build the condensation and print the components no edge enters; remove this block if you only need the components
    set<pair<int, int>> cedges;
    for (auto [a, b] : edges)
        if (comp[a] != comp[b]) cedges.insert({comp[a], comp[b]});
    vector<int> in(c + 1, 0);           // edges into each component
    for (auto [x, y] : cedges) in[y]++;
    for (int x = 1; x <= c; x++)
        if (in[x] == 0) cout << x << ' ';
    cout << '\n';
}

For the example it prints 4, then 3 3 3 4 1 1 1 2, then 1. Every edge goes to a component with a larger or equal number. Problem 1667 asks for exactly this numbering; remove the condensation block for it.

Each pass visits every vertex once and looks at every edge once, and building radj takes one more look at each edge, so the time is O(n + m) and the memory is O(n + m) for the two adjacency lists.

Building the condensation

The last block of the program goes over all the edges again, kept in edges while reading. For an edge from a to b with comp[a] != comp[b], the pair (comp[a], comp[b]) is an edge of the condensation. Several edges of the graph can join the same two components, so the pairs are collected in a set (or sort them and remove duplicates with unique); this takes O(m \log m). Then in[x] counts the edges into component x.

On the example cedges holds the 4 edges of Fig. 5, and only component 1 has in[1] == 0, so the last line is 1: one start, in the component of 5, 6 and 7, reaches every vertex.

Correctness proof

Number the finish positions of the first pass from 1 (finished first) to $n$. For a component $C$, let $f(C)$ be the largest finish position of a vertex in $C$. The proof uses this property of DFS: when dfs1(x) is called, every vertex that can be reached from $x$ along vertices not yet visited is visited and finished before dfs1(x) returns.

In words, a component finishes later than every component it has an edge to.

Lemma: if an edge goes from component $C$ to a different component $D$, then f(C) > f(D).

Take the first vertex $x$ of $C$ or $D$ that the first pass visits. At that moment no other vertex of $C$ or $D$ is visited.

• If $x$ is in $C$, then every vertex of $C$ and $D$ can be reached from $x$ through $C$, the edge into $D$ and then $D$, all of them unvisited. So they all finish before $x$ does, and $x$ is in $C$: f(C) > f(D).

• If $x$ is in $D$, then every vertex of $D$ finishes before dfs1(x) returns. No vertex of $C$ can be reached from $D$, otherwise $C$ and $D$ would be one component. So no vertex of $C$ is visited during dfs1(x), and all of $C$ is visited and finished later: f(C) > f(D).

Fig. 7. The number next to each vertex is its finish position. Every thick edge leaves a component with a larger largest number than the component it enters: 8 > 6 > 1 and 8 > 4 > 1.

Now the second pass. Suppose the components collected so far are correct, and the next vertex taken is $v$, the latest finished vertex not in a component yet. Its component $C$ then has the largest $f$ among the components not collected yet. An edge of radj that leaves $C$ is an edge u \to w of the graph with $u$ in another component $D$ and $w$ in $C$. By the lemma f(D) > f(C), so $D$ was collected earlier, \text{comp}_u \ne 0, and dfs2 doesn't go there. Inside $C$ every vertex can be reached from $v$ along reversed edges, because $C$ is strongly connected. So dfs2(v, c) gives the number $c$ to exactly the vertices of $C$. By induction, every component is collected correctly.

The same lemma gives the order: for an edge from $C$ to $D$, f(C) > f(D), so $C$ is collected first and gets the smaller number. The components come out in topological order of the condensation.

Common mistakes

• Taking order from the front and running dfs2 on adj, so a search can run on into another component, as the search from 7 collects 8 in the Explanation. Use radj and take order from the end.

• Recording a vertex when it is entered, not when it is finished, which breaks the order the second pass relies on and merges components. Append $v$ after the loop over its neighbours.

Similar algorithms

Cycle detection finds one cycle. A vertex lies on some cycle exactly when its component has at least two vertices or the vertex has an edge to itself.

Tarjan's algorithm finds the same components in O(n + m) with one DFS and no reversed graph. It finds them in reverse topological order, sinks first.

2-SAT builds a graph on the variables and their negations. The formula can be satisfied exactly when no variable is in the same component as its negation, and the order of the components gives the values.

DSU joins vertices along edges in both directions, so it answers the undirected question. With one-way edges 1 \to 2 and 2 \to 3 it puts 1, 2 and 3 into one set, although 3 can't reach 1.

Practice