Chapter 1 · Graphs and Models
Connectivity, Bridges, Articulation Points
What it means for a graph to hold together, and the two linear-time tests for its weakest points.
A connected component is a maximal set of vertices pairwise joined by a path. "Maximal" is doing work: components partition V, and two vertices in different components have no walk between them at all.
Counting components is the canonical first use of two tools:
// 1) DFS/BFS labelling — O(n+m), gives you the components themselves
vector<int> comp(n, -1);
int cc = 0;
for (int s = 0; s < n; s++) if (comp[s] == -1) {
stack<int> st{{s}}; comp[s] = cc;
while (!st.empty()) {
int u = st.top(); st.pop();
for (int v : g[u]) if (comp[v] == -1) { comp[v] = cc; st.push(v); }
}
cc++;
}
// 2) DSU — O((n+m) \u03b1(n)), and it *updates*: add edges online, ask "same component?"
DSU dsu(n);
for (auto [u, v] : given_edges) dsu.unite(u, v);
for (int q = 0; q < Q; q++) cout << (dsu.same(u, v) ? "YES\n" : "NO\n");Offline trick: a sequence of edge deletions becomes a sequence of insertions if you process the queries backwards. Insertions are union-find, deletions are not. This single reversal appears in dozens of problems — see Minimum Spanning Tree for the "which deletions disconnect the graph" version.
#Fragile parts
- A bridge (cut edge) is an edge whose removal increases the number of components.
- An articulation point (cut vertex) is a vertex whose removal does the same.
- A graph with |V| ≥ 3 and no articulation point is 2-connected (biconnected). A maximal 2-connected subgraph is a block; blocks glue together along cut vertices, forming the block-cut tree — a tree, which is why "the graph of blocks" supports tree DP.
An edge uv is a bridge ⇔ it lies on no cycle. A vertex v (not a root of the DFS tree) is an articulation point ⇔ it has a child c with no back edge from the subtree of c to a proper ancestor of v.
If uv lies on a cycle, deleting it leaves the rest of the cycle as an alternative route. Conversely, if uv is a tree edge of some DFS tree and the subtree below it contains no back edge escaping upward, then every route out of that subtree uses uv — so it is a bridge. For v and child c: if some edge from Tc reaches a strict ancestor of v, everything in Tc stays attached to v's parent when v is removed; otherwise Tc becomes a separate component. ∎
#The linear algorithm (low-link)
int timer = 0;
vector<int> tin(n, -1), low(n);
vector<char> is_bridge(m);
void dfs(int u, int pe) { // pe = index of the edge we arrived on
tin[u] = low[u] = timer++;
for (auto [v, id] : g[u]) {
if (id == pe) continue; // skip THAT edge, not that vertex: parallel edges matter
if (tin[v] != -1) low[u] = min(low[u], tin[v]); // back edge
else {
dfs(v, id);
low[u] = min(low[u], low[v]);
if (low[v] > tin[u]) is_bridge[id] = 1;
if (low[v] >= tin[u] && pe != -1) is_cut[u] = 1; // articulation point
}
}
// root: articulation point iff it has >1 DFS child (handled separately)
}- Comparing
v != parentinstead of comparing the edge id: with parallel edges the second copy is a real back edge and the bridge test wrongly fires. - Forgetting the root case for articulation points (it needs >1 child, since "no proper ancestor" is vacuous).
- Recursion depth. n = 2 × 105 on a path overflows the default stack: raise it (
ulimit -s unlimited, or#pragma comment(linker, "/STACK:…")locally) or write the iterative version.
Same graph, live report: components, bridges and cut vertices computed while you edit the edge list.
#Why anyone cares
- Bridge tree (contract every 2-edge-connected component) turns "number of edges on a path" questions into tree path queries — the standard reduction for "add one edge, how many bridges disappear", which is exactly diameter of the bridge tree's leaf-to-leaf distances when you may add one edge optimally.
- Block-cut tree converts vertex-biconnectivity questions into tree questions, where you already know the answers (Tree Diameter in Two Passes).
- A graph where every edge is a bridge is a forest; a graph with no bridges is one in which every edge belongs to a cycle. Those two extremes are the base cases of most induction proofs here.