*Written by Charlotte Knierim.*

Contents

This article assumes you are familiar with digraphs (directed graphs) and have already read the article about Preorder and Postorder.

In this article we look at strongly connected components of digraphs. Given a digraph, it is a natural question which vertices can be reached by a given vertex. A digraph is called strongly connected, if every vertex can be reached from every other vertex.

If a digraph is not strongly connected, then we can decompose it into strongly connected components. These are maximal sets in the graph such that every vertex in a set can be reached by every other vertex from the same set.

**Example:**

We can display the relationship between the strongly connected components in a component graph. The component graph is a DAG (directed acyclic graph). Note that there is a path from vertex $u$ to vertex $v$ if and only if there is a path from the component containing $u$ to the component containing $v$ in the component graph.

**Example:**

## Algorithm by Kosaraju

We show an algorithm that computes the strongly connected components of a digraph $D=(V,E)$ in $O(V+E)$. For this algorithm, we need the **transpose** $D^T =(V,E^T)$ that consists of all edges of $D$ reversed. Formally we add an edge $(u,v)$ to $E^T$ if $(v,u)$ was an edge in $E$.

Note that the strongly connected components of $D^T$ are exactly the same as the strongly connected components of $D$.

**Steps of the algorithm:**

- Perform a DFS in $D$ take note of the postorder of the vertices
- Create the transpose graph $D^T$
- Perform a DFS in $D^T$ according to the reverse postorder of the vertices

**Example:**
Starting the DFS at $c$ visiting $d$ and $e$ and then $a$ and $b$ and finally restarting the DFS at $f$ (because we cannot reach it from $c$) gives the following result. The number at each vertex indicates the postorder, the DFS edges are marked in red.

Keeping the postorder in mind, we now create the transposed graph $D^T$.

On the resulting graph $D^T$ we now perform a DFS starting at the vertex with the highest postorder (here $f$). Whenever we restart the DFS, we begin a new strongly connected component. Again the DFS edges are indicated in red.

### Implementation

Implementation in C++:

struct graph { int n; int num_comp = 0; vector<vector<int>> adjlist; vector<int> post; vector<int> comp; void dfs(int curr, int curr_comp = -2) { if (comp[curr] != -1) return; comp[curr] = curr_comp; for (auto nx : adjlist[curr]) dfs(nx, curr_comp); post.push_back(curr); } void kosaraju() { // Create list of vertices in post order comp.assign(n, -1); for (int i = 0; i < n; i++) dfs(i); // Reverse post order reverse(post.begin(), post.end()); // Build transpose graph vector<vector<int>> rev(n); for (int i = 0; i < n; i++) for (auto j : adjlist[i]) rev[j].push_back(i); swap(rev, adjlist); // Run dfs in reverse post order on transpose graph comp.assign(n, -1); for (int i = 0; i < n; i++) if (comp[post[i]] == -1) dfs(post[i], num_comp++); // Restore original graph swap(rev, adjlist); } };

**Remark** In the end we have a vector `comp` such that for any vertex $v$ we have that $v$ belongs to the strongly connected component `comp[v]`. We can now build the component graph in $O(E)$ by iterating over all edges of $D$ and for an edge $(u,v)\in E(D)$ adding the edge (`comp[u],comp[v]`) to the component graph if it is not contained already.