Bridges and Articulation Points

A bridge (cut edge) is an edge whose removal disconnects the graph. An articulation point (cut vertex) is a vertex whose removal does. Both identify single points of failure.

Low-link values

Run a DFS assigning each vertex an increasing timestamp tin[v]. Define

$\mathrm{low}[v]=\min \{\begin{array}{ll}\mathrm{tin}[v]& \\ \mathrm{tin}[u]& \text{for each back edge }v\to u\\ \mathrm{low}[c]& \text{for each child }c\end{array}$

In words: the earliest vertex reachable from $v$‘s subtree using tree edges plus at most one back edge.

Bridges — $O(V+E)$

Edge $(u,v)$ with $v$ a child is a bridge exactly when $\mathrm{low}[v]>\mathrm{tin}[u]$: nothing in $v$‘s subtree can reach $u$ or above without using that edge.

int timer_ = 0;
vector<int> tin, low;
vector<bool> visited;
vector<pair<int,int>> bridges;
 
void dfsBridge(int u, int pe) {              // pe = id of the edge we came from
    visited[u] = true;
    tin[u] = low[u] = timer_++;
    for (auto [v, id] : adj[u]) {
        if (id == pe) continue;              // skip the edge, not the vertex
        if (visited[v]) low[u] = min(low[u], tin[v]);
        else {
            dfsBridge(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > tin[u]) bridges.push_back({u, v});
        }
    }
}

Skip the edge, not the parent vertex

Passing the parent vertex and skipping it breaks on parallel edges: a doubled edge is not a bridge, but the vertex test wrongly reports it as one. Store edge ids in the adjacency list and skip the edge you arrived on. This is the single most common bug in bridge code.

Articulation points — $O(V+E)$

Almost the same DFS, with $\ge$ instead of $>$ and a special case at the root.

vector<bool> isArt;
 
void dfsArt(int u, int p) {
    visited[u] = true;
    tin[u] = low[u] = timer_++;
    int children = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (visited[v]) low[u] = min(low[u], tin[v]);
        else {
            dfsArt(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= tin[u] && p != -1) isArt[u] = true;
            children++;
        }
    }
    if (p == -1 && children > 1) isArt[u] = true;     // root special case
}

Why $\ge$ here but $>$ for bridges: for a bridge, $v$‘s subtree must not reach $u$ at all. For an articulation point it is enough that the subtree cannot reach above $u$ — reaching $u$ itself is fine, because removing $u$ still severs the subtree.

The root case: the DFS root has no parent above it, so it is a cut vertex exactly when it has two or more DFS-tree children (its subtrees are otherwise disconnected from each other).

Relationships

• Every bridge endpoint of degree $\ge 2$ is an articulation point.
• An articulation point need not be incident to any bridge (it can sit where two cycles meet).
• A graph with no bridges is 2-edge-connected; with no articulation points, 2-vertex-connected (biconnected).

What to build on top

Structure	Built from	Answers
Bridge tree	contract 2-edge-connected components	”how many bridges on the path $u\to v$”, edge connectivity
Block-cut tree	biconnected components + articulation points	”is $u$ on every path from $a$ to $b$”, vertex connectivity
Biconnected components	edge stack during the same DFS	maximal 2-connected pieces
Strong orientation	Robbins’ theorem	orient edges so the graph stays strongly connected — possible iff bridgeless

Typical problems

• “Which roads, if closed, disconnect the city?” — bridges
• “Which servers are critical?” — articulation points
• “Add the minimum edges to make the graph 2-edge-connected” — build the bridge tree, answer is $\lceil L/2\rceil$ where $L$ is its number of leaves
• “Count pairs of vertices separated by removing edge $e$” — subtree sizes on the bridge tree

See also: Tarjan’s Algorithm · Biconnected Components · DFS