Bridges and articulation points
Problem
In an undirected graph, a bridge is an edge whose removal increases the number of connected components. An articulation point is a vertex whose removal does the same. Find them all in O(V + E).
Example 1
Input: edges 1–0, 0–2, 2–1, 0–3, 3–4 Output: bridges: 0–3, 3–4 · articulation points: 0, 3
Also asked as: Find bridge in a graph
Test cases
Case 1
Input: 5, [[1,2,3],[0,2],[0,1],[0,4],[3]] Expected (any order): [[0,3],[3,4]]
Case 2
Input: 3, [[1],[0,2],[1]] Expected (any order): [[0,1],[1,2]]
Case 3
Input: 3, [[1,2],[0,2],[0,1]] Expected (any order): []
Case 4
Input: 1, [[]] Expected (any order): []
View solutionHide solution1 approach
1. Tarjan's DFS with discovery time & low-link
Time O(V + E)Space O(V)
low[u] = earliest discovery time reachable from u’s subtree via one back-edge. Edge (u, v) is a bridge iff low[v] > disc[u]; u is an articulation point iff some child has low[v] ≥ disc[u] (root: ≥ 2 DFS children).
function findBridges(n, adj) { const disc = new Array(n).fill(-1), low = new Array(n).fill(0); const bridges = []; let timer = 0; const dfs = (u, parent) => { disc[u] = low[u] = timer++; for (const v of adj[u]) { if (v === parent) continue; if (disc[v] === -1) { dfs(v, u); low[u] = Math.min(low[u], low[v]); if (low[v] > disc[u]) bridges.push([u, v]); } else { low[u] = Math.min(low[u], disc[v]); } } }; for (let i = 0; i < n; i++) if (disc[i] === -1) dfs(i, -1); return bridges;}