# Strongly Connected Components

Written by Charlotte Knierim.

Contents

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:

1. Perform a DFS in $D$ take note of the postorder of the vertices
2. Create the transpose graph $D^T$
3. 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<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);


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.