ayodhyya.comStrongly 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 Ayodhyya. Last updated June 1, 2026.
Kosaraju's Algorithm
Two-pass DFS: first pass on the original graph records finish times; second pass on the transposed graph processes nodes in decreasing finish-time order. Each DFS tree in the second pass is one SCC. Runs in O(V+E).
Tarjan's Algorithm
Single-pass DFS using low-link values and an explicit stack. A node is the root of an SCC when its low-link equals its DFS number. More efficient in practice than Kosaraju because it avoids building the transpose.
Why SCCs Matter
SCCs reveal cycles in dependency graphs, detect deadlocks in resource allocation, find communities in social networks, and optimize compilation by grouping mutually recursive functions.
Kosaraju's Algorithm
Two-pass DFS: first pass on the original graph records finish times; second pass on the transposed graph processes nodes in decreasing finish-time order. Each DFS tree in the second pass is one SCC. Runs in O(V+E).<\/p>
Tarjan's Algorithm
Single-pass DFS using low-link values and an explicit stack. A node is the root of an SCC when its low-link equals its DFS number. More efficient in practice than Kosaraju because it avoids building the transpose.<\/p>
Why SCCs Matter
SCCs reveal cycles in dependency graphs, detect deadlocks in resource allocation, find communities in social networks, and optimize compilation by grouping mutually recursive functions.<\/p>