The Low-Link Function & Cut Conditions
During a DFS of an undirected graph $G = (V, E)$, let $\text{tin}[u]$ be the discovery timestamp of vertex $u$. We define the low-link value $\text{low}[u]$ as the minimum discovery time $\text{tin}[w]$ of any vertex $w$ reachable from $u$ using zero or more DFS tree edges downward followed by at most one back edge upward:
$$\text{low}[u] = \min \begin{cases} \text{tin}[u] \\ \text{tin}[p] & \text{for all back edges } (u, p) \text{ (excluding the parent tree edge)} \\ \text{low}[v] & \text{for all DFS tree children } v \text{ of } u \end{cases}$$Let $(u, v)$ be a DFS tree edge where $u$ is the parent of $v$ ($\text{tin}[u] < \text{tin}[v]$):
- Bridge Condition (Strict Inequality): Tree edge $(u, v)$ is a bridge if and only if: $$\text{low}[v] > \text{tin}[u]$$ If $\text{low}[v] == \text{tin}[u]$, a back edge from $v$'s subtree reaches $u$ itself, forming a cycle that protects edge $(u, v)$ from being a bridge.
- Articulation Point Condition (Weak Inequality + Root Rule): A non-root vertex $u$ is an articulation point if and only if it has at least one DFS tree child $v$ satisfying: $$\text{low}[v] \ge \text{tin}[u]$$ Even if a back edge from $v$'s subtree reaches $u$ ($\text{low}[v] == \text{tin}[u]$), deleting vertex $u$ destroys both the tree edge $(u, v)$ and that back edge endpoint, isolating $v$'s subtree! Meanwhile, a DFS root $r$ is an articulation point if and only if $r$ has $\ge 2$ children in the DFS tree.
Biconnected Components (BCCs) & Block-Cut Trees
A maximal subgraph with no articulation points is called a Biconnected Component (2-vertex-connected component), and a maximal subgraph with no bridges is a 2-Edge-Connected Component. By pushing traversed edges onto an auxiliary stack during DFS and popping all edges down to $(u, v)$ whenever $\text{low}[v] \ge \text{tin}[u]$, Tarjan's algorithm partitions the edge set $E$ into biconnected components in $O(V + E)$ time. Contracting each 2-edge-connected component into a supernode yields the Bridge-Block Tree, turning cyclic graphs into trees where path queries can be answered via Lowest Common Ancestor (LCA).
Step through 0-1 BFS deque relaxation (push_front for w=0, push_back for w=1), Tarjan’s undirected bridge/articulation criterion (low[v] > tin[u] / low[v] ≥ tin[u]), and Tarjan’s single-pass SCC condensation.
Invariant & State
Because $\text{low}[u]$ depends only on $\text{tin}[v]$ of back-edge neighbors and $\text{low}[v]$ of tree children, both arrays $\text{tin}[0..V-1]$ and $\text{low}[0..V-1]$ occupy just $8V$ bytes ($8\text{ MB}$ for $V = 10^6$) and update in-place during DFS return without auxiliary heap structures.
Complexity Matrix
| Problem | Naive Deletion | Tarjan's DFS | Auxiliary Space |
|---|---|---|---|
| All Bridges (Cut-Edges) | O(E · (V + E)) | O(V + E) | O(V) |
| All Articulation Points | O(V · (V + E)) | O(V + E) | O(V) |
| Biconnected Components (BCC) | O(V · (V + E)) | O(V + E) | O(V + E) |
Production Implementation: Multigraph-Safe Tarjan Bridges & Cut Vertices
#include <vector>
#include <algorithm>
#include <utility>
struct UndirectedConnectivity {
struct Edge { int to; int id; };
int n, timer = 0;
std::vector<std::vector<Edge>> adj;
std::vector<int> tin, low;
std::vector<uint8_t> isCutVertex;
std::vector<std::pair<int, int>> bridges;
explicit UndirectedConnectivity(int vertices)
: n(vertices), adj(vertices), tin(vertices, 0), low(vertices, 0), isCutVertex(vertices, 0) {}
void addEdge(int u, int v, int id) {
adj[u].push_back({v, id});
adj[v].push_back({u, id});
}
void dfs(int u, int parentEdgeId) {
tin[u] = low[u] = ++timer;
int treeChildren = 0;
for (const auto& e : adj[u]) {
if (e.id == parentEdgeId) continue; // Safe even with parallel edges!
if (tin[e.to] != 0) {
// Back edge to ancestor
low[u] = std::min(low[u], tin[e.to]);
} else {
// Tree edge
++treeChildren;
dfs(e.to, e.id);
low[u] = std::min(low[u], low[e.to]);
if (low[e.to] > tin[u]) {
bridges.emplace_back(u, e.to);
}
if (parentEdgeId != -1 && low[e.to] >= tin[u]) {
isCutVertex[u] = 1;
}
}
}
if (parentEdgeId == -1 && treeChildren > 1) {
isCutVertex[u] = 1;
}
}
void solve() {
for (int i = 0; i < n; ++i) {
if (tin[i] == 0) dfs(i, -1);
}
}
};low[v] Instead of tin[v] on Back EdgesTwo subtle bugs plague Tarjan implementations: (1) Skipping the parent via if (v == parentVertex) continue; fails on multigraphs where two parallel edges connect $u$ and $v$—neither parallel edge is a bridge, so always pass parentEdgeId rather than parentVertex! (2) On a back edge $(u, v)$, updating low[u] = min(low[u], low[v]) instead of tin[v] breaks articulation point detection because $\text{low}$ is defined using at most one back edge without bypassing $v$ through a second back edge.