Introduction to Articulation Points and Bridges Pattern

Mechanism

An articulation point (cut vertex) is a vertex whose removal increases the number of connected components; a bridge is an edge with the same property. Tarjan's algorithm finds both in a single DFS pass by comparing each vertex's discovery time (when DFS first visits it) against the lowest discovery time reachable from its DFS-subtree using at most one back edge (its low value). If a child's subtree can only reach back up to the current vertex or lower, that child's subtree has no other way out of the graph — the current vertex is load-bearing.

Recognize the pattern

• Question mentions "critical connections", "single point of failure", "network stays connected if X is removed", or "minimum edges/servers to disconnect the network".
• Underlying structure is an undirected graph and the ask is about resilience/connectivity, not shortest path or ordering.
• Any request to find bridges or cut vertices in one pass, or to reason about a DFS tree's back edges.

Brute force → optimal

Brute force: for each vertex, delete it (and its edges), recount connected components via a fresh DFS/BFS, compare to baseline, restore. Repeating a full O(V+E) traversal for every vertex costs O(V·(V+E)) time, O(V+E) space per run.

Optimal (Tarjan, 1972): a single DFS computes disc[u] and low[u] for every vertex, deriving articulation points and bridges from tree-edge/back-edge comparisons — no repeated traversals. Cost drops to O(V+E) time, O(V) space.

Complexity, derived

DFS visits every vertex once and examines every edge exactly twice (undirected, once from each endpoint) — that is the definition of O(V+E) already; Tarjan's algorithm adds only O(1) work per edge examination (an array compare/update) and O(1) per vertex (initializing disc/low, a child counter for the root). No operation is repeated across vertices, so the total stays O(V+E) time. Space is the recursion stack plus three arrays of size V (disc, low, visited) → O(V), ignoring adjacency-list storage which is O(V+E) regardless of algorithm.

Compare to brute force's recurrence: T(V) = V × O(V+E) since each of the V removals re-runs a full traversal — that extra factor of V is exactly what the DFS-with-low-links trick eliminates by reusing the single traversal's back-edge information.

The two decision rules

Worked example

Graph: two triangles joined by one edge — edges (1,2) (2,3) (1,3) (3,4) (4,5) (4,6) (5,6). DFS from 1, adjacency visited in numeric order.

Result: articulation points {3, 4}; bridge {(3,4)}. Removing 3 or 4 splits the graph into the two triangles; removing the bridge edge alone does the same.

Java implementation

class ArticulationPointsAndBridges {
    private int timer = 0;
    private int[] disc, low;
    private boolean[] visited, isArt;
    private List<int[]> bridges = new ArrayList<>();
    private List<List<Integer>> adj;

    void run(int n, List<List<Integer>> adjacency) {
        adj = adjacency;
        disc = new int[n]; low = new int[n];
        visited = new boolean[n]; isArt = new boolean[n];
        for (int u = 0; u < n; u++)
            if (!visited[u]) dfs(u, -1);
    }

    private void dfs(int u, int parent) {
        visited[u] = true;
        disc[u] = low[u] = timer++;
        int children = 0;
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            if (visited[v]) {
                low[u] = Math.min(low[u], disc[v]); // back edge
            } else {
                children++;
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) bridges.add(new int[]{u, v});
                if (parent != -1 && low[v] >= disc[u]) isArt[u] = true;
            }
        }
        if (parent == -1 && children >= 2) isArt[u] = true;
    }
}

Pitfalls

• Forgetting to skip the parent edge: without if (v == parent) continue, the tree edge back to the parent is mistaken for a back edge, corrupting every low value upward.
• Using the parent check instead of a visited-edge-id check on multigraphs: if there are two parallel edges between u and parent, the parent check wrongly ignores a genuine second connection — track edge indices, not just the parent vertex, when parallel edges are possible.
• Applying the non-root rule to the root: the root has no vertex "above" it, so its articulation condition is child-count ≥ 2, not the low/disc comparison.
• Off-by-one on the bridge condition: bridge requires strict >; articulation point requires >= — swapping them misses articulation points that aren't bridge endpoints.

When to use / when not

Use Tarjan's low-link DFS whenever the question is about single points of failure, critical connections, or decomposing a graph into biconnected components — it is the only linear-time approach. Alternative — brute-force removal simulation: acceptable only for tiny graphs or as a correctness oracle in tests, since it costs an extra factor of V. Alternative — union-find rebuilt per removal: same O(V·(V+E)) ballpark, no better. Do NOT reach for this pattern for directed graphs (use Tarjan's strongly connected components algorithm instead, a different low-link application) or for weighted min-cut problems (use max-flow/min-cut, since articulation points only capture unweighted single-vertex/edge cuts, not general k-cuts).

Takeaways

• low[u] = earliest discovery time reachable from u's subtree via at most one back edge — the whole algorithm is one comparison of this value against disc[u].
• Bridge test is strict (>), articulation-point test is non-strict (>=) — the one-character difference matters.
• The DFS root needs a special-cased rule (≥2 children) because it has no ancestor to escape to.
• One DFS pass replaces V full re-traversals: O(V+E) vs O(V·(V+E)).

Recall question

In a DFS tree, vertex u (non-root) has exactly one child c with low[c] == disc[u]. Is u an articulation point, and is edge (u,c) a bridge?

Answer: u is an articulation point (condition is low[c] >= disc[u], satisfied). Edge (u,c) is NOT a bridge (condition requires strict low[c] > disc[u], which fails at equality) — c can reach back exactly to u via some other path, so removing the edge alone doesn't disconnect it, but removing u itself still does.

Based on Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms," SIAM Journal on Computing — the original low-link formulation underlying articulation point and bridge detection.