Articulation points and bridges — Tarjan's low-link values

The two key numbers

Formula Deriving the low-link recurrence from scratch

WHAT can $u$ reach climbing back up? Three sources:

Itself: $u$ can always "reach" its own discovery time → start $\text{low}[u]=\text{disc}[u]$ .
Through a tree child $v$ : anything the child's subtree can reach is also reachable from $u$ → take $\min(\text{low}[u], \text{low}[v])$ .
Through a back edge $u\to w$ (where $w$ is an ancestor, already visited, not the parent) → take $\min(\text{low}[u], \text{disc}[w])$ .

Putting it together: $\text{low}[u] = \min\Big(\text{disc}[u],\ \min_{\substack{v \text{ tree child}}}\text{low}[v],\ \min_{\substack{w \text{ back edge}}}\text{disc}[w]\Big)$

Why disc[w] and not low[w] for back edges? A back edge is not a tree edge — we only use it to record how high we jumped, which is exactly $\text{disc}[w]$ . Using $\text{low}[w]$ would double-count paths and give wrong results.

Bridge and articulation conditions

Figure — Articulation points and bridges — Tarjan's low-link values

Reference implementation

def tarjan(n, adj):
    disc = [-1]*n
    low  = [0]*n
    timer = [0]
    bridges, aps = [], set()
 
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        children = 0
        for v in adj[u]:
            if v == parent:
                continue                 # skip the edge we came down on
            if disc[v] == -1:            # tree edge
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))     # bridge:  strict >
                if parent != -1 and low[v] >= disc[u]:
                    aps.add(u)                 # AP non-root: >=
            else:                        # back edge
                low[u] = min(low[u], disc[v])
        if parent == -1 and children > 1:
            aps.add(u)                   # AP root: 2+ children
    for s in range(n):
        if disc[s] == -1:
            dfs(s, -1)
    return bridges, aps

Worked example 1 — a simple bridge

Graph: 0 - 1 - 2 and 2 - 3 - 2? Let's use edges $0\!-\!1,\ 1\!-\!2,\ 2\!-\!3,\ 3\!-\!1$ .

step	action	disc/low
visit 0	root	disc0=0, low0=0
→1 tree	child of 0	disc1=1, low1=1
→2 tree	child of 1	disc2=2, low2=2
→3 tree	child of 2	disc3=3, low3=3
3→1 back	back edge to 1	low3 = min(3, disc1=1) = 1
back to 2	low2 = min(2, low3=1) = 1
edge (2,3)?	low3=1 ≤ disc2=2 → not bridge
back to 1	low1 = min(1, low2=1) = 1
edge (1,2)?	low2=1 ≤ disc1=1 → not bridge
back to 0	low0 = min(0, low1=1) = 0
edge (0,1)?	low1=1 > disc0=0 → BRIDGE

Why this step? Subtree under 1 (the cycle 1-2-3) can climb back only to disc=1, never to 0. So $(0,1)$ is the lone link → bridge. Also vertex 1 (non-root) has child 2 with $\text{low}[2]=1 \ge \text{disc}[1]=1$ ⇒ 1 is an articulation point.

Worked example 2 — the root rule

Graph: star 1-0, 2-0, 3-0 (0 in the middle). DFS from 0.

0 is root, discovers children 1, 2, 3 as three separate tree children (no edges between them).
children count = 3 > 1 ⇒ 0 is an articulation point.

Why this step? Removing 0 leaves 1, 2, 3 fully isolated — the only paths between them passed through 0. The root rule (≥2 children) captures exactly this.

Active recall

Recall Predict before peeking (Forecast-then-Verify)

For a single cycle $0\!-\!1\!-\!2\!-\!3\!-\!0$ : how many bridges? How many articulation points?

Answer: Zero of each. Every edge is in the cycle, so each node has an alternate route — no single failure disconnects it. (Check: every $\text{low}[v] \le \text{disc}[\text{parent}]$ via the back edge that closes the cycle.)

Recall Feynman: explain to a 12-year-old

Picture a treehouse fort connected by rope bridges. You climb down ropes exploring new platforms. $\text{disc}$ is the order you reached each platform. $\text{low}$ is the highest platform you can swing back to using one secret shortcut rope. If a whole section of fort can only swing back to itself and never higher, the single rope holding it up is special — cut it and that section floats away (a bridge). And a platform everyone must pass through to get anywhere is a must-not-break support (an articulation point).

What is a bridge in a graph?

An edge whose removal increases the number of connected components.

What is an articulation point?

A vertex whose removal (with its edges) increases the number of connected components.

Definition of disc[u]?

The DFS discovery timestamp — order in which u is first visited.

Definition of low[u]?

The smallest discovery time reachable from u's subtree using tree edges down and at most one back edge.

Low-link recurrence?

low[u] = min(disc[u], min low[v] over tree children, min disc[w] over back edges).

Why use disc[w] (not low[w]) for a back edge?

A back edge only records how high we jumped; using low[w] would over-count and give wrong values.

Bridge condition for tree edge (u,v)?

low[v] > disc[u] (strict).

Articulation condition for non-root u with child v?

low[v] >= disc[u].

Articulation condition for the DFS root?

It has 2 or more DFS-tree children.

Why is bridge strict (>) but AP is (>=)?

Bridge deletes an edge; a back edge to u itself saves it. AP deletes vertex u; a back edge to u is useless once u is gone.

Time complexity of Tarjan's algorithm?

O(V + E), a single DFS pass.

What edge types appear in undirected DFS?

Only tree edges and back edges (no forward/cross edges).

Pitfall with parallel edges?

Skipping v==parent ignores a second parallel edge; track edge id and skip the parent edge only once.

Connections

Depth-First Search — the backbone traversal producing the DFS tree.
Strongly Connected Components - Tarjan — same low-link idea on directed graphs.
Biconnected Components — articulation points partition the graph into these.
Bridge Trees / 2-edge-connected components — contract non-bridge edges.
Connected Components — what bridges/cut vertices break apart.
Big-O Notation — why $O(V+E)$ matters.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek graph hai jisme cities aur roads hain. Bridge wo road hai jise hatao toh graph do tukdo me toot jaata hai. Articulation point wo city hai jise hatao toh bhi graph disconnect ho jaata hai. Ye dono "single point of failure" hote hain — agar yahi fail ho gaya toh network bikhar jaata hai. Tarjan ka algorithm ek hi DFS pass me sab nikal leta hai, $O(V+E)$ me.

Asli jugaad do numbers me hai: $\text{disc}[u]$ matlab "main is node pe kab pahuncha" (timestamp), aur $\text{low}[u]$ matlab "is node ke subtree se main upar kitna high climb kar sakta hoon — ek back edge use karke". Recurrence simple hai: apna disc se start karo, tree children ke low se min lo, aur back edge milne par us ancestor ke disc se min lo. Yaad rakho — back edge ke liye $\text{disc}[w]$ lena hai, $\text{low}[w]$ nahi, warna galat answer aayega.

Conditions: tree edge $(u,v)$ bridge hai jab $\text{low}[v] > \text{disc}[u]$ (strict greater, kyunki hum edge kaat rahe hain). Non-root vertex $u$ articulation point hai jab $\text{low}[v] \ge \text{disc}[u]$ (equal bhi chalega, kyunki hum poora vertex hata rahe hain). Aur DFS root articulation point tab hai jab uske 2 ya zyada tree children ho. Mnemonic: "Bridge Bigger, Articulation At-least." Bas yahi do signs yaad rakh lo, baaki sab derive ho jaayega.

Articulation points and bridges — Tarjan's low-link values

WHAT are we computing?

The two key numbers

Bridge and articulation conditions

Reference implementation

Worked example 1 — a simple bridge

Worked example 2 — the root rule

Active recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections