Practice › Graphs
Strongly Connected Components
Hard · Graphs · Asked at Amazon, Google, Microsoft, Samsung
In a directed graph, a strongly connected component is a maximal set of nodes where every node can reach every other. Print the number of strongly connected components.
Input
First line: n m. Next m lines: u v — an edge from u to v.
Output
The number of SCCs.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ m ≤ 2 · 10^5
Kosaraju: DFS to get finishing order, reverse all edges, then DFS in decreasing finish time — each new DFS is one SCC. Tarjan's algorithm does it in one pass.
Example 1
Input
5 5 1 2 2 3 3 1 3 4 4 5
Output
3
Example 2
Input
3 3 1 2 2 3 3 1
Output
1
Hints
- Kosaraju: first DFS records nodes in order of finishing time.
- Reverse every edge, then run DFS from nodes in decreasing finishing time; each DFS on the reversed graph visits exactly one SCC.
Approach
Pass 1: iterative DFS on the original graph pushing each node onto order when it finishes. Pass 2: on the reversed graph, take nodes from the end of order (latest finish first); each unvisited one starts a new component and a DFS marks everything it reaches. The node that finishes last lies in a "source" SCC of the condensation, and reversing edges stops the second DFS from leaking into other components. Iterative DFS avoids stack overflow for 10^5 nodes.
Complexity: O(n + m) time · O(n + m) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1), rg(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
rg[v].push_back(u);
}
vector<int> order, it(n + 1, 0);
vector<bool> seen(n + 1, false);
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
stack<int> st;
st.push(s);
seen[s] = true;
while (!st.empty()) {
int u = st.top();
if (it[u] < (int)g[u].size()) {
int v = g[u][it[u]++];
if (!seen[v]) seen[v] = true, st.push(v);
} else {
order.push_back(u);
st.pop();
}
}
}
vector<int> comp(n + 1, 0);
int c = 0;
for (int i = n - 1; i >= 0; i--) {
int s = order[i];
if (comp[s]) continue;
c++;
stack<int> st;
st.push(s);
comp[s] = c;
while (!st.empty()) {
int u = st.top();
st.pop();
for (int v : rg[u])
if (!comp[v]) comp[v] = c, st.push(v);
}
}
cout << c << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
g = [[] for _ in range(n + 1)]
rg = [[] for _ in range(n + 1)]
for i in range(m):
u, v = data[2 + 2 * i], data[3 + 2 * i]
g[u].append(v)
rg[v].append(u)
seen, order, it = [False] * (n + 1), [], [0] * (n + 1)
for s in range(1, n + 1):
if seen[s]:
continue
seen[s] = True
stack = [s]
while stack:
u = stack[-1]
if it[u] < len(g[u]):
v = g[u][it[u]]
it[u] += 1
if not seen[v]:
seen[v] = True
stack.append(v)
else:
order.append(stack.pop())
comp, c = [0] * (n + 1), 0
for s in reversed(order):
if comp[s]:
continue
c += 1
comp[s] = c
stack = [s]
while stack:
u = stack.pop()
for v in rg[u]:
if not comp[v]:
comp[v] = c
stack.append(v)
print(c)Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
List<List<Integer>> g = new ArrayList<>(), rg = new ArrayList<>();
for (int i = 0; i <= n; i++) { g.add(new ArrayList<>()); rg.add(new ArrayList<>()); }
for (int i = 0; i < m; i++) {
in.nextToken();
int u = (int) in.nval;
in.nextToken();
int v = (int) in.nval;
g.get(u).add(v);
rg.get(v).add(u);
}
int[] it = new int[n + 1], order = new int[n];
int cnt = 0;
boolean[] seen = new boolean[n + 1];
int[] st = new int[n + 1];
for (int s = 1; s <= n; s++) {
if (seen[s]) continue;
int top = 0;
st[top++] = s;
seen[s] = true;
while (top > 0) {
int u = st[top - 1];
if (it[u] < g.get(u).size()) {
int v = g.get(u).get(it[u]++);
if (!seen[v]) { seen[v] = true; st[top++] = v; }
} else {
order[cnt++] = u;
top--;
}
}
}
int[] comp = new int[n + 1];
int c = 0;
for (int i = n - 1; i >= 0; i--) {
int s = order[i];
if (comp[s] != 0) continue;
c++;
int top = 0;
st[top++] = s;
comp[s] = c;
while (top > 0) {
int u = st[--top];
for (int v : rg.get(u))
if (comp[v] == 0) { comp[v] = c; st[top++] = v; }
}
}
System.out.println(c);
}
}Solve Strongly Connected Components online · All practice problems