Bridges and articulation points

Hard

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): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}