Bridges & Articulation Points
O(n + m)One lowlink DFS finds every bridge (edge whose removal disconnects the graph) and articulation point (vertex whose removal does). Track parent edges by id so parallel edges are handled correctly. Recursive: mind the stack limit on large graphs.
// use it on
CSES: Necessary Roads ↗
The roads whose removal disconnects the network are the bridges, verbatim.
// the code
struct Cuts {
int n, timer = 0;
vector<vector<pair<int, int>>> adj; // {to, edge id}
vector<int> tin, low;
vector<bool> isArt;
vector<pair<int, int>> bridges;
Cuts(int n) : n(n), adj(n), tin(n, -1), low(n), isArt(n, false) {}
void add_edge(int id, int u, int v) {
adj[u].push_back({v, id});
adj[v].push_back({u, id});
}
void dfs(int u, int pe) { // pe = id of the edge we arrived by
tin[u] = low[u] = timer++;
int children = 0;
for (auto [v, id] : adj[u]) {
if (id == pe) continue;
if (tin[v] != -1) {
low[u] = min(low[u], tin[v]);
} else {
dfs(v, id);
low[u] = min(low[u], low[v]);
if (low[v] > tin[u]) bridges.push_back({u, v});
if (low[v] >= tin[u] && pe != -1) isArt[u] = true;
children++;
}
}
if (pe == -1 && children > 1) isArt[u] = true; // root rule
}
void run() {
for (int u = 0; u < n; u++)
if (tin[u] == -1) dfs(u, -1);
}
};// more connectivity