The challenge
Find every edge in an undirected graph whose removal increases the number of connected components.
Use edge IDs to distinguish parallel edges. Skip the exact parent edge, not every edge to the parent vertex.
Example
C–D and D–E are bridges. Edges around A–B–C–F–A lie on a cycle, so removing any one of them leaves another route.
Use the walkthrough below to inspect the input and each state change.
See Bridges, step by step
Follow the edges. Watch the state change.
Undirected · 6 vertices · 6 edgesA = 0, B = 1, …
CurrentVisited / acceptedUnvisited
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| — | — | — | — | — | — |
Step 01 / 15
Initialize discovery and low-link values.
low[u] is the earliest discovery reachable from u’s DFS subtree using tree edges and at most one back edge. Skip the parent edge by ID.
discovery = [-1] * V; timer = 0DFS path · top last
Empty
View input edges
A — B · A — F · B — C · C — F · C — D · D — E
Put it into code
A child subtree needs a back route to the parent or an ancestor to avoid a bridge.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
def find_cuts(n, edges):
# Undirected edges listed ONCE as (u, v).
# Edge IDs make parallel edges safe.
adj = [[] for _ in range(n)]
for edge_id, (u, v) in enumerate(edges):
adj[u].append((v, edge_id))
adj[v].append((u, edge_id))
discovery, low = [-1] * n, [-1] * n
bridges, articulation = [], set()
timer = 0
def visit(u, parent_edge=-1):
nonlocal timer
discovery[u] = low[u] = timer
timer += 1
children = 0
for v, edge_id in adj[u]:
if edge_id == parent_edge:
continue
if discovery[v] == -1:
children += 1
visit(v, edge_id)
low[u] = min(low[u], low[v])
if low[v] > discovery[u]:
bridges.append(edge_id)
if parent_edge != -1 and low[v] >= discovery[u]:
articulation.add(u)
else:
low[u] = min(low[u], discovery[v])
if parent_edge == -1 and children > 1:
articulation.add(u)
for u in range(n):
if discovery[u] == -1:
visit(u)
return bridges, sorted(articulation)#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
// Returns {bridge edge IDs, articulation vertices}.
std::pair<std::vector<int>, std::vector<int>> find_cuts(
int n, const std::vector<std::pair<int, int>>& edges) {
std::vector<std::vector<std::pair<int, int>>> adj(n);
for (int id = 0; id < static_cast<int>(edges.size()); ++id) {
auto [u, v] = edges[id];
adj[u].push_back({v, id});
adj[v].push_back({u, id});
}
std::vector<int> discovery(n, -1), low(n, -1), bridges, cuts;
std::vector<bool> articulation(n, false);
int timer = 0;
std::function<void(int, int)> visit = [&](int u, int parent_edge) {
discovery[u] = low[u] = timer++;
int children = 0;
for (auto [v, id] : adj[u]) {
if (id == parent_edge) continue;
if (discovery[v] == -1) {
++children;
visit(v, id);
low[u] = std::min(low[u], low[v]);
if (low[v] > discovery[u]) bridges.push_back(id);
if (parent_edge != -1 && low[v] >= discovery[u])
articulation[u] = true;
} else low[u] = std::min(low[u], discovery[v]);
}
if (parent_edge == -1 && children > 1) articulation[u] = true;
};
for (int u = 0; u < n; ++u) if (discovery[u] == -1) visit(u, -1);
for (int u = 0; u < n; ++u) if (articulation[u]) cuts.push_back(u);
return {bridges, cuts};
}