Bridges and Articulation Points

Quick Revisit

• USE WHEN: Finding edges/vertices whose removal disconnects an undirected graph
• INVARIANT: Edge (u,v) is a bridge iff low[v] > disc[u]; vertex u is an articulation point iff it has a child v with low[v] ≥ disc[u] (or u is root with ≥2 DFS children)
• TIME: O(V + E) | SPACE: O(V + E)
• CLASSIC BUG: Tracking parent by node ID fails on multigraphs — use edge index to skip only the specific edge you arrived on, not all edges to the parent
• PRACTICE: 05-ladder-graphs

Tarjan's DFS algorithm to find edges (bridges) and vertices (cut points) whose removal disconnects an undirected graph. Foundation for 2-edge-connected component decomposition and bridge trees. AL-22.

Difficulty: [Intermediate]Prerequisites: DFS and Tree DFSCF Rating Range: 1600-1900

---

Intuition

Consider this undirected graph on 6 vertices and 7 edges:

    0 ---- 1 ---- 2
    |      |      |
    |      3      |
    |             |
    4 ----------- 5

Edges: $(0,1),(1,2),(1,3),(2,5),(0,4),(4,5),(0,5)$.

Question: which edges, if removed, disconnect the graph? Which vertices?

Naive approach -- brute force each edge. For every edge $e$ among $m$ edges: remove $e$, run BFS/DFS from any vertex, check if all $n$ vertices are still reachable. If not, $e$ is a bridge.

• Each BFS costs $O(n+m)$.
• We repeat for each of $m$ edges.
• Total: $O(m\cdot (n+m))$.

For our example: $m=7$ edges, each BFS visits up to $n+m=6+7=13$ units of work. That is $7\times 13=91$ operations just for bridges. Repeat a similar approach for articulation points ($n$ removals): another $6\times 13=78$ operations.

On a contest graph with $n=2\times {10}^5$ and $m=5\times {10}^5$, the naive approach does roughly $5\times {10}^5\times 7\times {10}^5=3.5\times {10}^{11}$ operations. Far too slow. We need a single $O(n+m)$ pass.

During DFS, a back edge to an ancestor means there is an alternative path -- an edge is a bridge only if no back edge "jumps over" it.

Think of a road network. A bridge is a road where there is no detour: if that road is closed, some town becomes unreachable. A back edge in the DFS tree is exactly such a detour -- it provides a second route from a descendant back up to an ancestor, bypassing tree edges in between. If every tree edge on a path has some back edge jumping over it, none of those tree edges are bridges. An edge is a bridge precisely when the subtree below it has no back edge escaping upward past it.

The same idea extends to vertices. An articulation point is an intersection where every detour passes through it. Remove that intersection and traffic cannot flow between the parts it connected.

Visual Walkthrough

We DFS the 6-vertex graph above starting from vertex 0. At each vertex $v$, we record:

• $\text{disc}[v]$: the discovery time (order DFS first visits $v$).
• $\text{low}[v]$: the minimum discovery time reachable from the subtree of $v$ using tree edges downward and at most one back edge upward.

Step 1. Visit vertex 0. $\text{disc}[0]=0$, $\text{low}[0]=0$. Explore edge to 1.

  DFS tree so far:    0
                      |
  disc: [0, -, -, -, -, -]
  low:  [0, -, -, -, -, -]

Step 2. Visit vertex 1. $\text{disc}[1]=1$, $\text{low}[1]=1$. Explore edge to 2.

  DFS tree so far:    0 --- 1
                             |
  disc: [0, 1, -, -, -, -]
  low:  [0, 1, -, -, -, -]

Step 3. Visit vertex 2. $\text{disc}[2]=2$, $\text{low}[2]=2$. Explore edge to 5.

  DFS tree so far:    0 --- 1 --- 2
                                   |
  disc: [0, 1, 2, -, -, -]
  low:  [0, 1, 2, -, -, -]

Step 4. Visit vertex 5. $\text{disc}[5]=3$, $\text{low}[5]=3$. Explore edge to 4.

  DFS tree so far:    0 --- 1 --- 2 --- 5
                                         |
  disc: [0, 1, 2, -, -, 3]
  low:  [0, 1, 2, -, -, 3]

Step 5. Visit vertex 4. $\text{disc}[4]=4$, $\text{low}[4]=4$. Edge $(4,0)$ is a back edge since 0 is already visited. Update: $\text{low}[4]=min(4,\text{disc}[0])=min(4,0)=0$. No more unvisited neighbors. Return to 5.

  DFS tree:    0 --- 1 --- 2 --- 5 --- 4
               ^                       |
               +------ back edge ------+

  disc: [0, 1, 2, -, 4, 3]
  low:  [0, 1, 2, -, 0, 3]

Step 6. Back at vertex 5. Child 4 returned with $\text{low}[4]=0$. Update: $\text{low}[5]=min(3,0)=0$. Also, edge $(5,0)$ is a back edge: $\text{low}[5]=min(0,\text{disc}[0])=0$ (no change). Return to 2.

  low updated:  low[5] = 0

Step 7. Back at vertex 2. Child 5 returned with $\text{low}[5]=0$. Update: $\text{low}[2]=min(2,0)=0$. Return to 1.

  low updated:  low[2] = 0

Step 8. Back at vertex 1. Child 2 returned with $\text{low}[2]=0$. Update: $\text{low}[1]=min(1,0)=0$. Now explore edge to 3.

Step 9. Visit vertex 3. $\text{disc}[3]=5$, $\text{low}[3]=5$. No unvisited neighbors. No back edges. Return to 1.

  DFS tree (complete):

        0 --- 1 --- 2 --- 5 --- 4
              |            ^     ^
              3            |     |
                       back(5,0) back(4,0)

  Final values:
  +--------+------+-----+-------------------------------------+
  | vertex | disc | low | reason                              |
  +--------+------+-----+-------------------------------------+
  |   0    |   0  |  0  | root                                |
  |   1    |   1  |  0  | child 2 has low=0                   |
  |   2    |   2  |  0  | child 5 has low=0                   |
  |   3    |   5  |  5  | no back edges at all                |
  |   4    |   4  |  0  | back edge to 0: min(4, disc[0]) = 0 |
  |   5    |   3  |  0  | child 4 has low=0; back edge to 0   |
  +--------+------+-----+-------------------------------------+

Step 10. Check bridge condition on each tree edge $u\to v$: is $\text{low}[v]>\text{disc}[u]$?

  0->1:  low[1]=0 > disc[0]=0?  NO
  1->2:  low[2]=0 > disc[1]=1?  NO
  2->5:  low[5]=0 > disc[2]=2?  NO
  5->4:  low[4]=0 > disc[5]=3?  NO
  1->3:  low[3]=5 > disc[1]=1?  YES  --> BRIDGE!

Result: edge $(1,3)$ is the only bridge. Removing it isolates vertex 3. Vertices $\{0,1,2,4,5\}$ form one 2-edge-connected component; $\{3\}$ is alone.

Check articulation point condition for non-root vertices: is there a child $v$ with $\text{low}[v]\ge \text{disc}[u]$?

• Vertex 1: child 3 has $\text{low}[3]=5\ge \text{disc}[1]=1$. YES -- vertex 1 is an articulation point.
• Root vertex 0: has only 1 DFS child (vertex 1), so not an articulation point.

The Invariant: Two Conditions Side by Side

$\text{low}[u]$ = minimum discovery time reachable from the subtree rooted at $u$ via zero or more tree edges downward followed by at most one back edge upward.

The bridge and articulation-point conditions share low[] but differ by one character:

	Bridge (remove edge $u$-$v$)	Articulation point (remove vertex $u$)
Condition on tree edge $u\to v$	$\text{low}[v]>\text{disc}[u]$ (strict)	$\text{low}[v]\ge \text{disc}[u]$ (non-strict)
Root special case	none	root is AP iff it has $\ge 2$ DFS-tree children
Reading the invariant	"subtree of $v$ cannot reach $u$ or higher"	"subtree of $v$ cannot reach strictly above $u$"

Why the difference? Look at this two-triangle gadget:

       u
      / \
     a   b
      \ /
       v

In the DFS tree, $u\to a\to v$ is the spine. Edge $(b,v)$ comes back up; in this DFS, $\text{low}[a]=\text{low}[v]=\text{disc}[u]$ because the subtree can reach $u$ but not higher.

• Edge $u$-$a$: $\text{low}[a]=\text{disc}[u]$, so $\text{low}[a]>\text{disc}[u]$ is false. Not a bridge -- correct, because $b$ provides a detour.
• Vertex $u$: $\text{low}[a]=\text{disc}[u]$, so $\text{low}[a]\ge \text{disc}[u]$ is true. $u$ would be an AP if it were not the root, because removing $u$ destroys the only connection between $a$/$v$ and whatever lives above $u$. Reaching $u$ through a back edge does not save $a$ when $u$ itself is gone.

That is the entire reason for > vs >=: edges only sever the link they remove, but vertices take all their incident edges with them.

When to Reach for This

Trigger phrases in problem statements:

• "critical edge" or "critical link" -- bridge.
• "disconnect the graph by removing an edge/vertex" -- bridge or articulation point.
• "single point of failure" -- articulation point.
• "2-edge-connected" or "2-vertex-connected" -- decomposition using bridges/APs.
• "biconnected components" or "block-cut tree" -- articulation-point-based decomposition.
• "bridge tree" -- condense 2EC components, solve on tree.
• "orient edges to maximize strong connectivity" -- bridges constrain orientation.

Counter-examples -- when this is NOT the right tool:

• "Minimum number of edges to remove to disconnect $s$ from $t$" with removal count $>1$: this is max-flow / min-cut, not bridge finding (unless the answer is specifically 1).
• "Check if graph is connected": just run BFS/DFS. No need for Tarjan.
• "Find connected components": use BFS/DFS or DSU. Bridges/APs are for critical edges/vertices, not general connectivity.
• "Minimum spanning tree": completely different problem (Kruskal/Prim), even though both involve "critical edges."

What the Code Won't Teach You

low[v] is not just an array the DFS fills in. It answers a specific question: "Standing at vertex $v$, if I walk down the DFS tree and then take exactly one back edge up, how high (earliest discovery time) can I reach?" This is the invariant that makes bridges and articulation points computable in one pass. If low[v] feels like a magic number, you cannot adapt the algorithm to variations (parallel edges, directed graphs, online bridge finding).

  What low[v] answers:

                ancestor (disc = 2)
                   |
                  ...             low[v] = 2 means v's subtree
                   |              can reach disc-time 2 via
                   u (disc = 5)   tree edges ↓ then one back edge ↑
                   |
                   v (disc = 7)   If v's subtree had NO back edges:
                  / \             low[v] = disc[v] = 7
                ...  ...          -> edge u-v would be a bridge
                 ↑       |
                 +--back--+
                 edge to disc=2

The bridge tree is the payoff, not the bridge list. Finding bridges is step one. The real power comes from collapsing each 2-edge-connected component into a single node, keeping only bridge edges. The result is a tree -- the bridge tree -- and hard graph problems become tree problems (diameter, LCA, path queries). If you stop at "output the list of bridges," you are using 20% of the algorithm's potential.

  Graph -> Bridge tree transformation:

  Original:            2EC components:       Bridge tree:
  1--2--3--5--6        {1,2,3,4} {5,6,7}      [C1] --- [C2]
  |     |  |           bridge: (3,5)             |
  4-----+  7                                   edge = bridge (3,5)

  Any path query on the original graph reduces
  to a path query on this tree. Example:
  "Max bridges on any s-t path" = tree diameter.

The > vs >= distinction encodes a deep structural difference. For bridges (edge removal): if the subtree can reach $u$ itself via a back edge, the edge $(u,v)$ has a detour -- not a bridge. For articulation points (vertex removal): even if the subtree reaches $u$, removing $u$ destroys that connection. One character difference, completely different reasoning.

  > vs >= -- why they differ:

  Bridge (edge removal):           Artic. Point (vertex removal):
  low[v] > disc[u]                 low[v] >= disc[u]

    u ---- v                         u ---- v
    ^      |                         X      |
    |  back edge to u                (gone) |
    +------+                                |
                                     Reaching u doesn't help --
  Reaching u saves v's subtree.      u is removed!
  Edge u-v is NOT a bridge.          u IS an articulation point.

---

C++ STL Reference

There is no STL equivalent for bridge/AP finding. You implement Tarjan's DFS manually. The building blocks:

Feature	Header	Usage in Bridge/AP Code	Notes
vector<vector<pair<int,int>>>	<vector>	Adjacency list: adj[v] = {(to, edge_id), ...}	For bridge finding (need edge IDs)
vector<vector<int>>	<vector>	Simple adjacency list: adj[v] = {to, ...}	For AP finding (simpler)
function<void(int,int)>	<functional>	Recursive DFS lambda with captures	Slight overhead vs global function; fine for contests
auto [to, id]	(C++17)	Structured binding for pair	Clean iteration over adjacency list
min(a, b)	<algorithm>	Update low[v] values	Called $O(V+E)$ times total

---

Implementation (Contest-Ready)

Multigraph warning -- read this before copying the bridge code. Bridge-finding must skip the edge by edge index, not by parent vertex. If $u$ and $v$ are connected by two parallel edges and you skip every edge to the parent vertex, the algorithm hides the second edge from low[], falsely declaring the first edge a bridge. The template below stores pair<neighbor, edge_id> in the adjacency list and skips on id == par_edge. For articulation points, skipping by parent vertex is fine (removing a vertex removes all its incident edges anyway), so the AP template uses the simpler form -- but bridges must use edge IDs.

Version 1 -- Find All Bridges

Tracks edge IDs to correctly handle parallel edges.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    vector<vector<pair<int,int>>> adj(n); // {neighbor, edge_id}
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--; v--;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    vector<int> tin(n, -1), low(n);
    vector<bool> is_bridge(m);
    int timer = 0;

    // par_edge = edge ID used to enter v (skip it, not the whole parent vertex)
    function<void(int, int)> dfs = [&](int v, int par_edge) {
        tin[v] = low[v] = timer++;
        for (auto [to, id] : adj[v]) {
            if (id == par_edge) continue;
            if (tin[to] != -1) {
                low[v] = min(low[v], tin[to]); // back edge
            } else {
                dfs(to, id);
                low[v] = min(low[v], low[to]);
                if (low[to] > tin[v])           // strict >
                    is_bridge[id] = true;
            }
        }
    };

    // Handle disconnected graphs
    for (int v = 0; v < n; v++)
        if (tin[v] == -1)
            dfs(v, -1);

    vector<int> bridges;
    for (int i = 0; i < m; i++)
        if (is_bridge[i])
            bridges.push_back(i);

    printf("%d\n", (int)bridges.size());
    for (int id : bridges)
        printf("%d ", id + 1); // 1-indexed output
    if (!bridges.empty()) printf("\n");
}

Version 2 -- Find All Articulation Points

Uses parent-vertex tracking (simpler; correct for APs even with parallel edges).

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> tin(n, -1), low(n);
    vector<bool> is_ap(n);
    int timer = 0;

    function<void(int, int)> dfs = [&](int v, int parent) {
        tin[v] = low[v] = timer++;
        int children = 0;
        for (int to : adj[v]) {
            if (tin[to] != -1) {
                // Back edge (skip edges to parent vertex entirely)
                if (to != parent)
                    low[v] = min(low[v], tin[to]);
            } else {
                children++;
                dfs(to, v);
                low[v] = min(low[v], low[to]);
                // Non-root check: >= (not >)
                if (parent != -1 && low[to] >= tin[v])
                    is_ap[v] = true;
            }
        }
        // Root special case: AP iff >= 2 DFS-tree children
        if (parent == -1 && children > 1)
            is_ap[v] = true;
    };

    for (int v = 0; v < n; v++)
        if (tin[v] == -1)
            dfs(v, -1);

    vector<int> aps;
    for (int v = 0; v < n; v++)
        if (is_ap[v])
            aps.push_back(v);

    printf("%d\n", (int)aps.size());
    for (int v : aps)
        printf("%d ", v + 1);
    if (!aps.empty()) printf("\n");
}

---

ASCII Trace: Tarjan's Bridge-Finding on a 6-Node Graph

Graph (undirected):           Adjacency list:
  0 ─── 1 ─── 2               0: [1, 2]
  |   / |                      1: [0, 2, 3]
  |  /  |                      2: [0, 1]
  | /   |                      3: [1, 4, 5]
  2     3                      4: [3, 5]
        |╲                     5: [3, 4]
        4 ─ 5

DFS from node 0 (parent shown in brackets):

Step  Visit   Parent  disc[]                  low[]                   Notes
──────────────────────────────────────────────────────────────────────────────
 1    0       -       [0,-,-,-,-,-]           [0,-,-,-,-,-]
 2    1       0       [0,1,-,-,-,-]           [0,1,-,-,-,-]
 3    2       1       [0,1,2,-,-,-]           [0,1,2,-,-,-]
      2->0 back edge                           low[2]=min(2,disc[0])=0
 4    backtrack 2->1   [0,1,2,-,-,-]           [0,0,0,-,-,-]          low[1]=min(1,low[2])=0
 5    3       1       [0,1,2,3,-,-]           [0,0,0,3,-,-]
 6    4       3       [0,1,2,3,4,-]           [0,0,0,3,4,-]
 7    5       4       [0,1,2,3,4,5]           [0,0,0,3,4,5]
      5->3 back edge                           low[5]=min(5,disc[3])=3
 8    backtrack 5->4   [0,1,2,3,4,5]           [0,0,0,3,3,3]          low[4]=min(4,low[5])=3
 9    backtrack 4->3   [0,1,2,3,4,5]           [0,0,0,3,3,3]          low[3]=min(3,low[4])=3
10    backtrack 3->1   [0,1,2,3,4,5]           [0,0,0,3,3,3]          low[1]=min(0,low[3])=0

Bridge check for each tree edge (u->v): bridge iff low[v] > disc[u]
  0->1: low[1]=0 > disc[0]=0?  NO
  1->2: low[2]=0 > disc[1]=1?  NO
  1->3: low[3]=3 > disc[1]=1?  YES  <- BRIDGE *
  3->4: low[4]=3 > disc[3]=3?  NO
  4->5: low[5]=3 > disc[4]=4?  NO

Bridges found: {1-3}

---

Operations Reference

Operation	Time	Space
Build adjacency list	$O(V+E)$	$O(V+E)$
DFS (find all bridges)	$O(V+E)$	$O(V+E)$
DFS (find all APs)	$O(V+E)$	$O(V+E)$
Build bridge tree / 2EC decomposition	$O(V+E)$	$O(V+E)$
Total (single pass)	$O(V+E)$	$O(V+E)$

Everything runs in a single DFS pass. No sorting, no log factors. The $O(V+E)$ is tight -- you visit every vertex and traverse every edge exactly twice (once per direction).

---

Problem Patterns & Tricks

Pattern 1 -- Direct bridge finding

Description: Given an undirected graph, output all bridges. Pure Tarjan application. Read graph, run DFS, check low[v] > tin[u] for each tree edge.

Example problems:

• UVa 796 -- Critical Links (classic)
• Any graph connectivity problem where you need to identify critical edges.

Pattern 2 -- Direct articulation point finding

Description: Given an undirected graph, output all cut vertices. Handle the root case separately.

Example problems:

• SPOJ SUBMERGE -- Submerging Islands (classic)
• CF 193C -- Cutting Figure (~1700)

Pattern 3 -- 2-edge-connected decomposition (bridge tree)

Description: Collapse each 2EC component into a single node. Bridges become edges of the resulting tree. Now solve the problem on a tree (LCA, DP, diameter, etc.).

Construction: run DFS, mark bridges. Then BFS/DFS ignoring bridges to label components.

// After finding bridges, label 2EC components:
vector<int> comp(n, -1);
int num_comp = 0;
for (int v = 0; v < n; v++) {
    if (comp[v] != -1) continue;
    queue<int> q;
    q.push(v);
    comp[v] = num_comp;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto [to, id] : adj[u]) {
            if (comp[to] == -1 && !is_bridge[id]) {
                comp[to] = num_comp;
                q.push(to);
            }
        }
    }
    num_comp++;
}
// Build bridge tree: for each bridge edge, add edge between comp[u] and comp[v].

Example problems:

• CF 1000E -- We Need More Bosses (~2100) -- build bridge tree, find its diameter.
• CF 652E -- Pursuit For Artifacts (~2100) -- bridge-aware path query.

Pattern 4 -- Edge orientation for strong connectivity

Description: Orient all edges of an undirected graph so that the resulting directed graph is "as connected as possible." Non-bridge edges within a 2EC can always be oriented to form a strongly connected component. Bridge edges are forced into one direction. Maximize the minimum SCC size.

Example problems:

• CF 732F -- Tourist Reform (~2300)

Pattern 5 -- Block-cut tree (biconnected components by vertices)

Description: A biconnected component is a maximal subgraph with no articulation point. The block-cut tree has two types of nodes: blocks (biconnected components) and cut vertices. An edge connects a cut vertex to every block it belongs to. Use this to answer queries about vertex removal.

Example problems:

• CF 962F -- Simple Cycles Edges (~2300)

Pattern 6 -- Removing critical edges to disconnect specific vertices

Description: Find the minimum number of edges to remove to disconnect $s$ from $t$. If there's a bridge on the $s$-$t$ path (in the bridge tree), one removal suffices. More advanced variants ask for removing 1-2 specific edges.

Example problems:

• CF 700C -- Break Up (~2500)

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|  BRIDGES & ARTICULATION POINTS  --  CHEAT SHEET              |
+--------------------------------------------------------------+
|  WHEN TO USE:                                                 |
|    - "Which edges/vertices are critical for connectivity?"    |
|    - 2-edge-connected decomposition / bridge tree             |
|    - Prereq for edge orientation, block-cut tree              |
+--------------------------------------------------------------+
|  BRIDGE:  tree edge u->v where  low[v] >  tin[u]   (strict)  |
|  ART.PT:  non-root u, child v:  low[v] >= tin[u]   (non-str) |
|           OR root u with >= 2 DFS children                    |
+--------------------------------------------------------------+
|  TEMPLATE (bridges, handles parallel edges):                  |
|    tin[v] = low[v] = timer++;                                 |
|    for (auto [to, id] : adj[v]) {                             |
|        if (id == par_edge) continue;                          |
|        if (tin[to] != -1) low[v] = min(low[v], tin[to]);     |
|        else { dfs(to, id);                                    |
|               low[v] = min(low[v], low[to]);                  |
|               if (low[to] > tin[v]) bridge(id); }             |
|    }                                                          |
+--------------------------------------------------------------+
|  PARALLEL EDGES: track edge ID, not parent vertex             |
|  ROOT AP: count DFS children, ignore low values               |
+--------------------------------------------------------------+
|  TIME: O(V + E)         SPACE: O(V + E)                      |
+--------------------------------------------------------------+

---

Gotchas & Debugging

> vs >= -- the #1 source of WA

Bridges: low[v] > tin[u]. Articulation points: low[v] >= tin[u]. Mixing them up gives subtly wrong results. Mnemonic: for a bridge (edge removal), reaching $u$ is enough to save the subtree. For an AP (vertex removal), reaching $u$ doesn't help because $u$ is gone -- you need to reach above $u$.

low[v] definition matters. low[v] = minimum discovery time reachable from the subtree of v using at most one back edge.

Bridge condition: Edge (u,v) is a bridge if low[v] > tin[u] (strictly greater). Articulation point condition: Vertex u is an AP if low[v] >= tin[u] (greater or equal).

The > vs >= difference is critical:

• Bridge: no back edge from v's subtree reaches u or above -> removing the edge disconnects.
• AP: no back edge from v's subtree reaches ABOVE u -> removing u disconnects (but u itself being reachable doesn't help).

Getting > vs >= wrong silently misclassifies edges/vertices.

Parallel edges and parent tracking

If you skip edges by parent vertex (not edge ID), two parallel edges between $u$ and $v$ will both be skipped, falsely making them look like bridges. Always use edge IDs for bridge finding. For articulation points, skipping by parent vertex is correct (removing a vertex removes all its edges, including parallel ones), but be aware the low values differ from the edge-ID version.

Root articulation point

The root of the DFS tree is an articulation point only if it has $\ge 2$ DFS-tree children. The low condition doesn't apply to the root -- it has no ancestors to be cut off from. Forgetting this special case is a common bug.

tin[] initialization

Initialize tin[] to $-1$, not $0$. Vertex 0 gets tin[0] = 0 during DFS. If you initialize to $0$, you cannot distinguish "visited at time 0" from "unvisited." This causes DFS to skip vertex 0's component entirely.

Stack overflow on deep graphs

For $n\le 2\cdot {10}^5$, recursive DFS usually works. For $n\ge 5\cdot {10}^5$, you may hit the default stack limit. Fixes:

• Linux contest machines: ulimit -s unlimited or compile with -Wl,-z,stacksize=....
• Iterative DFS: more code, but no stack limit issues.

Disconnected graphs

Always loop over all vertices and start DFS from every unvisited one. A single dfs(0, -1) misses other components:

for (int v = 0; v < n; v++)
    if (tin[v] == -1)
        dfs(v, -1);

Debugging tips

• Print tin[] and low[] arrays after DFS. Verify low[v] <= tin[v] for all $v$.
• For a suspected bridge $(u,v)$: check that removing it actually disconnects the graph (BFS/DFS without that edge).
• A graph with no bridges is 2-edge-connected. A graph with no APs is 2-vertex-connected (biconnected).
• If your DFS explores vertices in an unexpected order, check adjacency list construction -- did you add both directions?

Mental Traps

"Finding all bridges automatically gives me all articulation points."

Wrong. A vertex can be an articulation point without any of its incident edges being bridges. Consider a vertex connecting two separate cycles -- removing it splits the graph, but no single edge removal does. Bridges and articulation points use similar DFS but check different conditions (> vs >=) and require separate logic.

  Vertex 3 is an articulation point, but has NO incident bridges:

      1 --- 2             Remove vertex 3:
      |     |               cycle {1,2} and cycle {4,5}
      +--3--+               become disconnected
      |     |
      4 --- 5             Remove any single edge:
                            graph stays connected (cycles provide detours)
  
  Bridges:  NONE
  Artic. points: {3}      <- These sets are NOT subsets of each other

"I can skip the edge-index tracking and just check to != parent."

This works for simple graphs but silently breaks on multigraphs. If vertices $u$ and $v$ have two parallel edges, skipping by parent vertex causes both edges to be ignored. The second edge is a genuine back edge that proves $u$-$v$ is NOT a bridge -- missing it falsely marks $(u,v)$ as a bridge. Always use edge indices for bridge finding.

  Parallel edges between u and v:

    u ===== v       (two edges: e0 and e1)
     edge0  edge1

  DFS enters v from u via e0.
  Skip by parent vertex: skip BOTH e0 and e1
    -> low[v] never sees u -> falsely declares bridge!

  Skip by edge index: skip only e0, process e1 as back edge
    -> low[v] = min(low[v], disc[u]) -> correctly NOT a bridge

---

Common Mistakes

1. Skipping all edges to the parent on parallel edges. Bridge-finding code works on simple graphs but misses bridges when there are parallel edges. The cause: if (to != parent) to skip the parent in the DFS. With parallel edges from $u$ to $v$, both edges have to == parent, and the code skips all of them -- treating both as the tree edge. Fix: track the edge index of the edge you used to arrive at $v$, and only skip that specific edge, not all edges to the parent.

Debug Drills

Drill 1 -- Bridge condition uses wrong inequality

if (low[to] >= disc[v])  // Finds articulation points, not bridges!
    bridges.push_back({v, to});

What's wrong?

For bridges, the condition is low[to] > disc[v] (strict). The >= condition is for articulation points. With >=, back edges that reach exactly node $v$ would be falsely classified as bridges:

if (low[to] > disc[v])
    bridges.push_back({v, to});

Drill 2 -- Root articulation point: checking wrong condition

if (parent == -1 && children > 0)  // BUG: should be > 1
    is_cut[v] = true;

What's wrong?

The root is an articulation point only if it has 2 or more DFS-tree children. With 1 child, removing the root just detaches one subtree but doesn't split it:

if (parent == -1 && children > 1)
    is_cut[v] = true;

Drill 3 -- Multi-edge: skipping all edges to parent

void dfs(int v, int parent) {
    for (auto [to, id] : adj[v]) {
        if (to == parent) continue;  // BUG: skips ALL edges to parent
        // ...
    }
}

What's wrong?

With parallel edges, you must skip only the specific edge you arrived on, not all edges to the parent node. Use the edge index:

void dfs(int v, int parent_edge) {
    for (auto [to, id] : adj[v]) {
        if (id == parent_edge) continue;  // skip only the arrival edge
        // ...
    }
}

Self-Test

Before moving to practice problems, verify you can answer these without looking at the notes:

• [ ] Write Tarjan's bridge-finding DFS from memory, using edge indices (not parent vertex) to handle parallel edges correctly.
• [ ] State the bridge condition (low[v] > disc[u]) and articulation point condition (low[v] >= disc[u]) and explain why one uses strict and the other non-strict inequality.
• [ ] Explain the root special case for articulation points -- the DFS root is an AP iff it has $\ge 2$ DFS-tree children -- and why the low condition fails for the root.
• [ ] Describe how to build a bridge tree: find bridges, label 2-edge-connected components via BFS ignoring bridges, then create a tree node per component with bridge edges between them.
• [ ] Given a graph with $n=6$ vertices, trace Tarjan's DFS and compute disc[] and low[] arrays, identifying all bridges and articulation points.

Practice Problems

CF Rating	What You Should Be Able to Do
1200	Know that removing a bridge disconnects the graph; find bridges by brute force (remove each edge, check connectivity).
1500	Implement Tarjan's $O(V+E)$ algorithm for bridges and articulation points; handle the root special case.
1800	Build the bridge tree (2-edge-connected component condensation); solve problems on the bridge tree.
2100	Handle multi-edges (parallel edges), online bridge finding, or combine bridge analysis with LCA / tree DP.

#	Problem	Source	Difficulty	Key Idea
1	Submerging Islands	SPOJ	Easy	Count articulation points directly
2	Critical Links	UVa 796	Easy	Find and sort all bridges
3	Network	UVa 315	Easy	Count articulation points
4	Cutting Figure	CF 193C	Medium	Check if any articulation point exists in a grid graph
5	Pursuit For Artifacts	CF 652E	Medium-Hard	Bridge-aware path search between $s$ and $t$
6	We Need More Bosses	CF 1000E	Medium-Hard	Bridge tree + find tree diameter
7	Simple Cycles Edges	CF 962F	Hard	Find edges in biconnected components with exactly one cycle
8	Tourist Reform	CF 732F	Hard	Orient edges using 2EC decomposition
9	Break Up	CF 700C	Hard	Remove 1-2 edges to disconnect $s$ from $t$ using bridge analysis
10	Necessary Roads	CSES	1800	Find all bridges in an undirected graph
11	Necessary Cities	CSES	1800	Find all articulation points

---

Further Reading

• cp-algorithms -- Finding Bridges -- detailed reference with proof of correctness and parallel-edge handling.
• cp-algorithms -- Finding Articulation Points -- includes the root special case and iterative variant.
• cp-algorithms -- Bridge Tree / 2EC Components -- online bridge finding and condensation.
• CF Blog -- DFS Tree and Back Edges -- excellent tutorial on DFS tree properties and applications.
• Tarjan 1972 -- "Depth-First Search and Linear Graph Algorithms" -- the original paper introducing DFS-based decomposition.
• For prerequisite DFS concepts, see: 03-dfs-and-tree-dfs.md
• For DSU-based connectivity (simpler problems), see: ../../01-data-structures/05-disjoint-set/11-union-find-dsu.md

Related Techniques

• Block-Cut Tree -- compresses biconnected components found by Tarjan's algorithm into a tree
• DFS and Tree DFS -- bridge-finding is a direct extension of DFS with low-link values
• SCC and 2-SAT -- Tarjan's SCC algorithm uses the same discovery/low framework on directed graphs

---