Pattern Guide
Advanced Graph: SCC, Bridges & 2-SAT
"Tarjan finds everything: SCCs, bridges, articulation points — one DFS."
Advanced graph algorithms detect critical structure: Strongly Connected Components (Kosaraju/Tarjan), bridges (edges whose removal disconnects), articulation points (vertices whose removal disconnects), and 2-SAT (satisfiability for pairs of boolean variables). These appear in hard graph problems.
22 min readgraph problems →
Problems you can solve with this pattern
4 problems · click any to start solving
Kosaraju's SCC — two DFS passes
function kosaraju(n, adj) {
const vis = new Array(n).fill(false);
const order = [];
// Pass 1: DFS on original, record finish order
const dfs1 = (u) => {
vis[u] = true;
for (const v of adj[u]) if (!vis[v]) dfs1(v);
order.push(u);
};
for (let i = 0; i < n; i++) if (!vis[i]) dfs1(i);
// Transpose graph
const radj = Array.from({length:n}, ()=>[]);
for (let u = 0; u < n; u++) for (const v of adj[u]) radj[v].push(u);
// Pass 2: DFS on transposed in reverse finish order
vis.fill(false);
const sccs = [];
const dfs2 = (u, scc) => {
vis[u] = true; scc.push(u);
for (const v of radj[u]) if (!vis[v]) dfs2(v, scc);
};
while (order.length) {
const u = order.pop();
if (!vis[u]) { const scc = []; dfs2(u, scc); sccs.push(scc); }
}
return sccs; // each array = one SCC
}Once you've mastered BFS/DFS for basic traversal, the next level is finding critical structure in graphs: Which edges are bridges (removal disconnects the graph)? Which vertices are articulation points? Which nodes are strongly connected (can reach each other)? These all use variants of one DFS with timestamps and low values.
Strongly Connected Components (Kosaraju)
SCC: A maximal subgraph where every node can reach every other. Kosaraju's algorithm:
1. DFS on original graph; push nodes to stack in FINISH order
2. Transpose the graph (reverse all edges)
3. DFS on transposed graph in reverse finish order — each DFS tree = one SCC
Tarjan's algorithm does it in one pass using disc (discovery time) and low (minimum discovery time reachable).
1. DFS on original graph; push nodes to stack in FINISH order
2. Transpose the graph (reverse all edges)
3. DFS on transposed graph in reverse finish order — each DFS tree = one SCC
Tarjan's algorithm does it in one pass using disc (discovery time) and low (minimum discovery time reachable).
Kosaraju's SCC — two DFS passes
function kosaraju(n, adj) {
const vis = new Array(n).fill(false);
const order = [];
// Pass 1: DFS on original, record finish order
const dfs1 = (u) => {
vis[u] = true;
for (const v of adj[u]) if (!vis[v]) dfs1(v);
order.push(u);
};
for (let i = 0; i < n; i++) if (!vis[i]) dfs1(i);
// Transpose graph
const radj = Array.from({length:n}, ()=>[]);
for (let u = 0; u < n; u++) for (const v of adj[u]) radj[v].push(u);
// Pass 2: DFS on transposed in reverse finish order
vis.fill(false);
const sccs = [];
const dfs2 = (u, scc) => {
vis[u] = true; scc.push(u);
for (const v of radj[u]) if (!vis[v]) dfs2(v, scc);
};
while (order.length) {
const u = order.pop();
if (!vis[u]) { const scc = []; dfs2(u, scc); sccs.push(scc); }
}
return sccs; // each array = one SCC
}Bridges and Articulation Points (Tarjan)
Tarjan's bridge/articulation point algorithm
function findBridgesAndAP(n, adj) {
const disc = new Array(n).fill(-1); // discovery time
const low = new Array(n).fill(0); // min disc reachable via back edges
const bridges = [], aps = new Set();
let timer = 0;
const dfs = (u, parent) => {
disc[u] = low[u] = timer++;
let childCount = 0;
for (const v of adj[u]) {
if (disc[v] === -1) { // tree edge
childCount++;
dfs(v, u);
low[u] = Math.min(low[u], low[v]);
// Bridge: no back edge from subtree of v reaches above u
if (low[v] > disc[u]) bridges.push([u, v]);
// Articulation point:
if (parent === -1 && childCount > 1) aps.add(u); // root with 2+ children
if (parent !== -1 && low[v] >= disc[u]) aps.add(u); // non-root
} else if (v !== parent) { // back edge (not to direct parent)
low[u] = Math.min(low[u], disc[v]);
}
}
};
for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
return { bridges, aps: [...aps] };
}
// KEY INSIGHT:
// low[v] = min discovery time reachable from subtree of v using back edges
// Bridge (u,v): low[v] > disc[u] — subtree of v can't reach u or above without edge u-v
// AP u: low[v] >= disc[u] for some child v — subtree of v needs u to connect to restWhen to use advanced graph algorithms:
- "Which edges/nodes are critical?" → Bridges/Articulation Points (Tarjan)
- "Which nodes can reach each other in directed graph?" → SCC (Kosaraju/Tarjan)
- "Minimum edges to make strongly connected?" → Condense to DAG, count in/out-degree 0 nodes
- "Satisfiability with pairs of boolean constraints?" → 2-SAT (build implication graph, SCC)
Tarjan's low-link values:
- disc[u]: discovery time (when we first visit u)
- low[u]: minimum disc reachable from subtree of u via back edges
- Bridge: edge (u,v) where low[v] > disc[u]
- Articulation point: vertex u where low[v] >= disc[u] for some child v
- "Which edges/nodes are critical?" → Bridges/Articulation Points (Tarjan)
- "Which nodes can reach each other in directed graph?" → SCC (Kosaraju/Tarjan)
- "Minimum edges to make strongly connected?" → Condense to DAG, count in/out-degree 0 nodes
- "Satisfiability with pairs of boolean constraints?" → 2-SAT (build implication graph, SCC)
Tarjan's low-link values:
- disc[u]: discovery time (when we first visit u)
- low[u]: minimum disc reachable from subtree of u via back edges
- Bridge: edge (u,v) where low[v] > disc[u]
- Articulation point: vertex u where low[v] >= disc[u] for some child v