Strongly Connected Components
Compress a directed graph into its mutually reachable blocks, then reason on the resulting DAG instead of the original cycles.
Strongly Connected Components
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Strongly connected components are the natural building blocks of directed graphs with cycles. Inside one SCC, every vertex can reach every other. Once those components are collapsed, the graph becomes a DAG, and many problems become much easier.
When to Use It
Use SCC decomposition when:
the graph is directed and reachability inside cycles matters,
the problem asks about mutual reachability or cycle groups,
a graph with cycles should be reduced to a DAG before DP or counting.
Core Idea
Kosaraju's algorithm uses two DFS passes:
one DFS on the original graph to record finishing order,
one DFS on the reversed graph in reverse finishing order to extract components.
Key Insight
The finishing order from the first pass places SCCs in a useful reverse-topological arrangement. When the second pass starts from the latest unfinished vertex on the reversed graph, it captures exactly one SCC at a time.
Operations / Main Technique
build the reverse graph,
first DFS for finishing order,
second DFS for component assignment,
optionally build the condensation DAG.
Worked example.
If vertices \(\{1,2,3\}\) can all reach each other, they form one SCC no matter how many internal edges they have. A single edge leaving that group becomes one edge in the condensation DAG.
Correctness Intuition
In the condensation DAG, finishing times in the first pass place source components late enough that the reversed-graph DFS can collect them without leaking into another unassigned component. Repeating that process partitions the graph exactly into SCCs.
Complexity Analysis
Kosaraju runs in \(O(n + m)\) time and \(O(n + m)\) memory.
Implementation
The code returns:
a component id for each vertex,
the list of vertices in each component.
That is enough to build a condensation graph afterward if needed.
Common Pitfalls
Forgetting to build the reversed graph.
Reusing the visited array incorrectly between the two DFS passes.
Confusing SCCs with weakly connected components.
Variants / Extensions
Tarjan's one-pass SCC algorithm.
2-SAT by SCC on the implication graph.
DAG DP after condensation.
Practice Problems
Count SCCs in a directed graph.
Build and analyze the condensation DAG.
Solve 2-SAT or reachability constraints through SCC decomposition.
References
Code
Contest-ready reference implementation for the idea explained above.
struct StronglyConnectedComponents {
int n;
vector<vector<int>> graph;
vector<vector<int>> reverse_graph;
vector<int> order;
vector<int> comp_id;
vector<vector<int>> components;
explicit StronglyConnectedComponents(int n)
: n(n), graph(n), reverse_graph(n), comp_id(n, -1) {}
void add_edge(int u, int v) {
graph[u].push_back(v);
reverse_graph[v].push_back(u);
}
void dfs1(int v, vector<int>& seen) {
seen[v] = 1;
for (int to : graph[v]) {
if (!seen[to]) {
dfs1(to, seen);
}
}
order.push_back(v);
}
void dfs2(int v, int id) {
comp_id[v] = id;
components.back().push_back(v);
for (int to : reverse_graph[v]) {
if (comp_id[to] == -1) {
dfs2(to, id);
}
}
}
void build() {
vector<int> seen(n, 0);
for (int v = 0; v < n; ++v) {
if (!seen[v]) {
dfs1(v, seen);
}
}
reverse(order.begin(), order.end());
for (int v : order) {
if (comp_id[v] == -1) {
components.push_back({});
dfs2(v, (int)components.size() - 1);
}
}
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.