Pattern Guide
Bridges & Articulation Points
"Find critical edges and vertices. DFS with low[] array. O(V+E)."
A bridge is an edge whose removal disconnects the graph. An articulation point (cut vertex) is a node whose removal disconnects the graph. Both found via Tarjan's DFS in O(V+E): compute disc[v] (discovery time) and low[v] (minimum discovery time reachable via back edges). Bridge: low[child] > disc[parent]. Articulation: low[child] ≥ disc[node] (with root check).
Problems you can solve with this pattern
3 problems · click any to start solving
function findBridgesAndCuts(n, edges) {
const adj = Array.from({length: n}, () => []);
for (const [u, v, id] of edges) {
adj[u].push([v, id]);
adj[v].push([u, id]);
}
const disc = new Array(n).fill(-1);
const low = new Array(n).fill(0);
const bridges = [], cuts = [];
let timer = 0;
function dfs(u, parentEdgeId) {
disc[u] = low[u] = timer++;
let children = 0;
for (const [v, eid] of adj[u]) {
if (disc[v] === -1) {
children++;
dfs(v, eid);
low[u] = Math.min(low[u], low[v]);
// Bridge check: v's subtree can't reach u or above
if (low[v] > disc[u]) bridges.push(eid);
// Articulation point: non-root with low[v] >= disc[u]
if (parentEdgeId !== -1 && low[v] >= disc[u]) cuts.push(u);
} else if (eid !== parentEdgeId) {
// Back edge (not parent): update low
low[u] = Math.min(low[u], disc[v]);
}
}
// Root is articulation point iff it has >= 2 DFS children
if (parentEdgeId === -1 && children >= 2) cuts.push(u);
}
for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
return { bridges: [...new Set(bridges)], cuts: [...new Set(cuts)] };
}DFS tree edges go from parent to child. Back edges go from descendant to ancestor. low[v] = minimum of disc[v] and disc of all ancestors reachable via back edges from v's subtree. A back edge "supports" the forward edge above it. Edge (u,v) where u is parent: bridge if low[v] > disc[u] (v's subtree can't reach u or above without this edge). Node u: articulation point if some child v has low[v] ≥ disc[u] (or u is root with ≥2 children).
function findBridgesAndCuts(n, edges) {
const adj = Array.from({length: n}, () => []);
for (const [u, v, id] of edges) {
adj[u].push([v, id]);
adj[v].push([u, id]);
}
const disc = new Array(n).fill(-1);
const low = new Array(n).fill(0);
const bridges = [], cuts = [];
let timer = 0;
function dfs(u, parentEdgeId) {
disc[u] = low[u] = timer++;
let children = 0;
for (const [v, eid] of adj[u]) {
if (disc[v] === -1) {
children++;
dfs(v, eid);
low[u] = Math.min(low[u], low[v]);
// Bridge check: v's subtree can't reach u or above
if (low[v] > disc[u]) bridges.push(eid);
// Articulation point: non-root with low[v] >= disc[u]
if (parentEdgeId !== -1 && low[v] >= disc[u]) cuts.push(u);
} else if (eid !== parentEdgeId) {
// Back edge (not parent): update low
low[u] = Math.min(low[u], disc[v]);
}
}
// Root is articulation point iff it has >= 2 DFS children
if (parentEdgeId === -1 && children >= 2) cuts.push(u);
}
for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1);
return { bridges: [...new Set(bridges)], cuts: [...new Set(cuts)] };
}- Bridge (u,v): low[v] > disc[u] (strictly greater)
- Articulation non-root: low[v] ≥ disc[u] for any child v (≥, not >)
- Articulation root: root has ≥ 2 DFS tree children
low[v] definition: min of disc[v], disc of back-edge ancestors reachable from v's subtree
Bridge tree: Contract each 2-edge-connected component to a node. Bridges become the tree edges. Useful for "after removing bridge, how many nodes in each component?"
Parallel edges: Use edge IDs (not parent node) to avoid counting back-edge on duplicate edges as a bridge.