The challenge
Find vertices in an undirected graph whose removal, together with their incident edges, increases the number of connected components.
The DFS root has a different rule from other vertices. Distinguish DFS children from ordinary graph degree.
Example
C and D are articulation points. Removing C separates D and E from the cycle; removing D isolates E.
Use the walkthrough below to inspect the input and each state change.
See Articulation points, step by step
Follow the edges. Watch the state change.
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| — | — | — | — | — | — |
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
View input edges
A — B · A — F · B — C · C — F · C — D · D — E
Put it into code
A vertex is a cut point when it is the only connection from a DFS child subtree to the rest.
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};
}