Strongly Connected Components from Scratch (2026)
Strongly Connected Components (SCCs) partition a directed graph into maximal subgraphs where every vertex is reachable from every other vertex within the subgraph. SCCs reveal the cyclic structure of a graph.
Kosaraju's and Tarjan's algorithms are the two classic linear-time approaches for finding SCCs, each with distinct implementation strategies.
Kosaraju's Algorithm
Kosaraju's algorithm performs two DFS passes: the first fills a stack in finishing order, and the second processes vertices in that order on the transposed graph. Each DFS in the second pass yields one SCC.
With O(V+E) time, it is simple to implement but requires graph transposition, doubling memory usage for large graphs.
void dfs1(int u, vector>& graph, vector& visited, stack& st) {
visited[u] = true;
for (int v : graph[u])
if (!visited[v]) dfs1(v, graph, visited, st);
st.push(u);
}
void dfs2(int u, vector>& trans, vector& visited, vector& comp) {
visited[u] = true;
comp.push_back(u);
for (int v : trans[u])
if (!visited[v]) dfs2(v, trans, visited, comp);
}
vector> kosaraju(vector>& graph) {
int V = graph.size();
vector visited(V, false);
stack st;
for (int i = 0; i < V; i++)
if (!visited[i]) dfs1(i, graph, visited, st);
vector> trans(V);
for (int u = 0; u < V; u++)
for (int v : graph[u]) trans[v].push_back(u);
fill(visited.begin(), visited.end(), false);
vector> sccs;
while (!st.empty()) {
int u = st.top(); st.pop();
if (!visited[u]) {
vector comp;
dfs2(u, trans, visited, comp);
sccs.push_back(comp);
}
}
return sccs;
} Tarjan's Algorithm
Tarjan's algorithm finds SCCs in a single DFS pass using discovery time and low-link values. A vertex is an SCC root when its low-link equals its discovery time, at which point the SCC is popped from the stack.
It avoids graph transposition and is more memory-efficient than Kosaraju, though its recursive nature may overflow the stack on large graphs.
void tarjanDFS(int u, vector>& graph, vector& disc, vector& low,
vector& inStack, stack& st, vector>& sccs, int& time) {
disc[u] = low[u] = ++time;
st.push(u); inStack[u] = true;
for (int v : graph[u]) {
if (disc[v] == -1) {
tarjanDFS(v, graph, disc, low, inStack, st, sccs, time);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) low[u] = min(low[u], disc[v]);
}
if (low[u] == disc[u]) {
vector comp;
while (true) {
int v = st.top(); st.pop();
inStack[v] = false;
comp.push_back(v);
if (v == u) break;
}
sccs.push_back(comp);
}
} Frequently Asked Questions
What is the difference between Kosaraju and Tarjan?
Kosaraju uses two DFS passes and requires graph transposition but is simpler. Tarjan uses one DFS pass with low-link values, avoiding transposition but requiring careful recursion management.
What are real-world applications of SCCs?
SCCs are used in compilers for dependency analysis, in web page ranking algorithms, in formal verification for detecting cycles in state machines, and in social network analysis.
Originally published on Ayodhyyya. Last updated June 1, 2026.