Bridges and Articulation Points
Use DFS lowlink values to find edges or vertices whose removal disconnects an undirected graph.
Bridges and Articulation Points
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Bridges and articulation points identify the fragile parts of an undirected graph. A bridge is an edge whose removal disconnects the graph. An articulation point is a vertex whose removal does the same.
When to Use It
Use these routines when:
the problem asks which roads, links, or nodes are critical,
the graph is undirected and connectivity under deletions matters,
biconnected structure is more relevant than shortest paths.
Core Idea
Run DFS and compute:
\(\texttt{tin[v]}\): the DFS entry time,
\(\texttt{low[v]}\): the smallest entry time reachable from \(v\)'s subtree using tree edges and at most one back edge.
These values tell whether a subtree can reconnect to an ancestor without using its parent edge.
Key Insight
If a child subtree of \(v\) cannot reach an ancestor of \(v\), then the edge to that child is a bridge. The same structural failure also tells when \(v\) separates that subtree from the rest of the graph.
Operations / Main Technique
DFS with parent tracking,
update \(\texttt{low}\) from tree children and back edges,
test bridge condition \(\texttt{low[to] > tin[v]}\),
test articulation condition with the root and non-root cases separated.
Worked example.
If child \(\texttt{to}\) of \(v\) has \(\texttt{low[to] > tin[v]}\), then the subtree rooted at \(\texttt{to}\) has no back edge reaching \(v\) or above. So removing edge \((v, to)\) disconnects that subtree.
Correctness Intuition
The lowlink value summarizes the highest ancestor reachable from the subtree. If that reach does not climb above the parent edge, then the parent edge is the only connection upward. That is exactly the bridge condition. The articulation condition is the vertex version of the same idea.
Complexity Analysis
With adjacency lists, the algorithm runs in \(O(n + m)\) time and \(O(n)\) extra memory.
Implementation
The sample collects both:
all bridges,
all articulation points.
It assumes a simple undirected graph. Multiedges need a little extra care in the parent-edge handling.
Common Pitfalls
Forgetting the special root case for articulation points.
Mishandling multiedges or self-loops.
Updating \(\texttt{low}\) with the wrong endpoint on back edges.
Treating the algorithm as if it worked unchanged on directed graphs.
Variants / Extensions
Edge-biconnected and vertex-biconnected components.
Bridge tree after contracting 2-edge-connected components.
Offline connectivity reasoning with lowlink as a subroutine.
Practice Problems
List all bridges in a network.
Count articulation points.
Contract components after removing bridges and run tree DP on the result.
References
Code
Contest-ready reference implementation for the idea explained above.
struct BridgesAndArticulationPoints {
int n;
vector<vector<int>> graph;
vector<int> tin;
vector<int> low;
vector<int> seen;
vector<int> is_articulation;
vector<pair<int, int>> bridges;
int timer = 0;
explicit BridgesAndArticulationPoints(int n)
: n(n), graph(n), tin(n, -1), low(n, -1), seen(n, 0), is_articulation(n, 0) {}
void add_edge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfs(int v, int parent = -1) {
seen[v] = 1;
tin[v] = low[v] = timer++;
int child_count = 0;
for (int to : graph[v]) {
if (to == parent) continue;
if (seen[to]) {
low[v] = min(low[v], tin[to]);
} else {
dfs(to, v);
low[v] = min(low[v], low[to]);
if (low[to] > tin[v]) {
bridges.push_back({v, to});
}
if (parent != -1 && low[to] >= tin[v]) {
is_articulation[v] = 1;
}
++child_count;
}
}
if (parent == -1 && child_count > 1) {
is_articulation[v] = 1;
}
}
void build() {
for (int v = 0; v < n; ++v) {
if (!seen[v]) {
dfs(v);
}
}
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.