---
title: "Connectivity, Bridges, Articulation Points"
summary: What it means for a graph to hold together, and the two linear-time tests for its weakest points.
difficulty: core
tags: [connectivity, DFS, low-link]
time: n + m
space: n
prereq: [foundations/representation, trees/dfs]
see: [flow/cuts, structures/dsu]
---

:::definition label="Components"
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:

```cpp components.cpp
// 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");
```

:::note title="Adding edges vs deleting edges"
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 @advanced-tree/mst for the "which deletions disconnect the graph" version.
:::

## Fragile parts
:::definition label="Bridge, cut vertex, 2-connected"
- 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| \ge 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.
:::

:::theorem title="Characterisation"
An edge $uv$ is a bridge $\iff$ it lies on no cycle.
A vertex $v$ (not a root of the DFS tree) is an articulation point $\iff$ it has a child $c$ with no back edge from the subtree of $c$ to a *proper ancestor* of $v$.
:::

:::proof
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 $T_c$ reaches a strict ancestor of $v$, everything in $T_c$ stays attached to $v$'s parent when $v$ is removed; otherwise $T_c$ becomes a separate component. ∎
:::

## The linear algorithm (low-link)

```cpp bridges.cpp
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)
}
```

:::warning title="Three classic implementation bugs"
1. Comparing `v != parent` instead of comparing the *edge id*: with parallel edges the second copy is a real back edge and the bridge test wrongly fires.
2. Forgetting the root case for articulation points (it needs $>1$ child, since "no proper ancestor" is vacuous).
3. Recursion depth. $n = 2 \times 10^5$ on a path overflows the default stack: raise it (`ulimit -s unlimited`, or `#pragma comment(linker, "/STACK:…")` locally) or write the iterative version.
:::

:::demo id="graph-explorer" caption="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 $\text{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 (@trees/diameter).
- 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.

:::problems
- [[CSES 2076]] Necessary Roads | https://cses.fi/problemset/task/2076 | core | bridges
- [[CSES 1685]] New Flight Routes | https://cses.fi/problemset/task/1685 | hard | bridges, orientation
- [[CF 1000E]] We Need More Bosses | https://codeforces.com/problemset/problem/1000/E | hard | bridge tree, diameter
- [[CSES 1666]] Building Roads | https://cses.fi/problemset/task/1666 | easy | components
:::