Pattern Reference
Strongly Connected Components
"Kosaraju's, Tarjan's algorithm. Condensation DAG, 2-SAT, dominator trees."
Loading...
Deep Dive Tutorial
Tarjan's SCC: DFS with discovery time and low-link values. low[v] = min discovery time reachable from subtree of v (via back/cross edges). If low[v] == disc[v], v is root of an SCC — pop stack until v. Kosaraju's: (1) DFS on original graph, push to stack in finish order. (2) Transpose graph. (3) DFS on transposed graph in reverse finish order — each DFS tree is one SCC. Both O(V+E).
Tarjan's SCC algorithm
function tarjanSCC(graph, n) {
const disc = new Array(n).fill(-1);
const low = new Array(n).fill(0);
const onStack = new Array(n).fill(false);
const stack = [];
const sccs = [];
let timer = 0;
function dfs(u) {
disc[u] = low[u] = timer++;
stack.push(u);
onStack[u] = true;
for (const v of (graph[u] || [])) {
if (disc[v] === -1) {
dfs(v);
low[u] = Math.min(low[u], low[v]);
} else if (onStack[v]) {
low[u] = Math.min(low[u], disc[v]);
}
}
// u is root of an SCC
if (low[u] === disc[u]) {
const scc = [];
let w;
do {
w = stack.pop();
onStack[w] = false;
scc.push(w);
} while (w !== u);
sccs.push(scc);
}
}
for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i);
return sccs; // SCCs in reverse topological order
}Worked Problems
rotate-ccw
Tarjan's SCC key insight: low[v] = min discovery time reachable via any path (back edges). If low[v] == disc[v], v is the root of an SCC — everything on the stack above v forms the SCC.
Condensation DAG: After finding SCCs, contract each SCC to a single node. The result is a DAG — useful for 2-SAT, shortest path in graphs with cycles.
Bridges vs SCCs: Bridge = edge not in any SCC of size ≥ 2. Articulation point = vertex whose removal increases component count. Both use the same low-link technique.
Condensation DAG: After finding SCCs, contract each SCC to a single node. The result is a DAG — useful for 2-SAT, shortest path in graphs with cycles.
Bridges vs SCCs: Bridge = edge not in any SCC of size ≥ 2. Articulation point = vertex whose removal increases component count. Both use the same low-link technique.