Bridges and Articulation Points — Critical Edges and Cut Vertices [LC 1192, Google, Meta]

Problem Statement#

Given an undirected connected graph with n vertices and m edges, identify every bridge and every articulation point. A bridge is an edge whose removal disconnects the graph. An articulation point (or cut vertex) is a vertex whose removal disconnects the graph. Solve in O(V + E) using Tarjan's low-link DFS.

Constraints:

• 1 <= n <= 10^5
• n - 1 <= m <= 2 * 10^5
• The graph is undirected and connected; no self-loops; multi-edges may exist.

Example:

Input:  n = 5, edges = [[0,1],[1,2],[2,0],[1,3],[3,4]]
Output: bridges = [[1,3],[3,4]], articulation_points = [1,3]
Explanation: Edge (1,3) is a bridge because removing it isolates {3,4}.
             Edge (3,4) is a bridge because removing it isolates {4}.
             Vertex 1 is an articulation point: removing it disconnects {3,4} from {0,2}.
             Vertex 3 is an articulation point: removing it disconnects {4}.

Why This Problem Matters#

Bridges and articulation points are the structural weak points of any network. In fault-tolerant system design, they are exactly the components that must be replicated to keep the system alive when any single failure occurs. Telecom companies look for bridges to identify single-link points of failure between regions; AWS examines articulation points in service-dependency graphs to flag fragile components; Twitter's friend graph analysis uses bridges to detect community boundaries.

LeetCode 1192 (Critical Connections in a Network) is the canonical interview rendering of this problem and frequently appears at Google, Meta, and Amazon onsites. Knowing the bridge-finding algorithm signals to interviewers that you have absorbed the deepest part of DFS theory: discovery times and low-link values. Articulation points use the same machinery with one tweak, so once you have one, the other is essentially free.

The technique transfers directly to biconnected components decomposition, which is used in computer-aided design (CAD) for circuit layout, in transport network resilience studies, and in some compiler optimizations involving CFGs (control flow graphs).

The Core Insight#

The same disc[u] and low[u] values that drive Tarjan's SCC algorithm also detect bridges and articulation points in undirected graphs.

Bridge condition: edge (u, v) is a bridge iff low[v] > disc[u] where v is a child of u in the DFS tree. The strict inequality means no back edge from v or its subtree can reach u or anything earlier than u. So removing (u, v) truly disconnects the graph.

Articulation point conditions:

• If u is the root of the DFS tree, u is an articulation point iff u has at least two children in the DFS tree.
• If u is not the root, u is an articulation point iff there exists a child v such that low[v] >= disc[u]. The non-strict inequality is the key difference from bridges: a back edge that lands exactly at u does not save u from being a cut vertex, but it does save the edge from being a bridge.

The DFS itself is the same as Tarjan's SCC variant, except undirected graphs have no need for an onStack array — every visited neighbour is either the immediate DFS parent (skip it) or a true back edge.

When relaxing low[u] from a neighbour v, you must avoid the edge back to parent[u]. The cleanest way is to compare against the parent and skip exactly once (in case of multi-edges, use edge IDs).

Visual Dry Run#

Edges: 0-1, 1-2, 2-0, 1-3, 3-4. DFS from 0.

For articulation points: vertex 1 has child 3 with low[3] = 3 >= disc[1] = 1, so 1 is an articulation point. Vertex 3 has child 4 with low[4] = 4 >= disc[3] = 3, so 3 is also an articulation point.

Result: bridges {(1,3), (3,4)}, articulation points {1, 3}.

Solution (Optimal)#

Python#

import sys
from collections import defaultdict
 
def find_bridges_and_aps(n, edges):
    sys.setrecursionlimit(10**6)
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
 
    disc = [-1] * n
    low = [0] * n
    bridges = []
    aps = set()
    timer = [0]
 
    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0  # count of DFS-tree children of u
 
        for v in adj[u]:
            if disc[v] == -1:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                # Bridge check: no back edge from v or below reaches u or earlier
                if low[v] > disc[u]:
                    bridges.append((u, v))
                # Articulation point check (non-root):
                if parent != -1 and low[v] >= disc[u]:
                    aps.add(u)
            elif v != parent:
                # back edge to ancestor (not the immediate parent)
                low[u] = min(low[u], disc[v])
 
        # Root articulation: more than one DFS-tree child
        if parent == -1 and children > 1:
            aps.add(u)
 
    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return bridges, sorted(aps)

JavaScript#

function findBridgesAndAPs(n, edges) {
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const disc = new Array(n).fill(-1);
    const low  = new Array(n).fill(0);
    const bridges = [];
    const aps = new Set();
    let timer = 0;
 
    function dfs(u, parent) {
        disc[u] = low[u] = timer++;
        let children = 0;
 
        for (const v of adj[u]) {
            if (disc[v] === -1) {
                children++;
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) bridges.push([u, v]);
                if (parent !== -1 && low[v] >= disc[u]) aps.add(u);
            } else if (v !== parent) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        if (parent === -1 && children > 1) aps.add(u);
    }
 
    for (let i = 0; i < n; i++) {
        if (disc[i] === -1) dfs(i, -1);
    }
    return { bridges, aps: [...aps].sort((a,b)=>a-b) };
}

Complexity: Time O(V + E) because every vertex is visited once and every edge processed twice (once from each endpoint). Space O(V) for arrays plus the recursion stack.

Common Mistakes#

1. Treating multi-edges with the parent check naively. If two edges connect u and v, then v -> u should not be treated as the parent edge twice. Use edge IDs and a usedEdge[] set for safety.
2. Using strict inequality for articulation points. Bridges use >, articulation points use >=. Mixing them up is the classic bug.
3. Not handling the root specially. A non-root cut vertex needs low[v] >= disc[u]. The root needs at least two DFS-tree children. Forgetting either case undercounts or overcounts.
4. Relaxing low against the parent. Skip the immediate parent edge once. If you forget, every internal vertex looks like a "back edge" and low collapses to the parent's disc.
5. Treating the graph as directed. Bridges and articulation points are defined for undirected graphs only. Directed analogues (strong bridges, SCC structure) use Tarjan's SCC.
6. Stack overflow. Same caveat as Tarjan SCC — deep chains can blow the recursion stack. Use iterative DFS for n up to 10^5.

Interview Tips#

• State the bridge formula and the articulation formula side by side. Interviewers want to see that you understand the subtle inequality difference.
• For LeetCode 1192, the answer is exactly the list of bridges. Mention this connection explicitly.
• Mention that the algorithm is sometimes called Tarjan's bridge-finding algorithm.
• For the multi-edge edge case, mention edge-IDs as the robust fix instead of vertex-parent comparison.
• If the graph is disconnected, run DFS from every unvisited vertex; the same logic handles forests.

Follow-up Questions#

1. How do you find biconnected components? Maintain an edge stack. When a vertex closes (no remaining children), pop edges off until you remove the closing edge — they form one biconnected component.
2. What is a 2-edge-connected component? It is the equivalence class under "connected by two edge-disjoint paths." Equivalent to graph minus all bridges.
3. Detect bridges online (as edges are added)? Use offline-online union-find on the bridge-tree.
4. LeetCode 1192: Direct application — output every bridge.
5. What is the chain decomposition algorithm? A modern alternative to Tarjan's bridge-finding that is often easier to code and reason about.

Key Takeaways#

• A bridge is an edge whose removal disconnects the graph; an articulation point is a vertex whose removal disconnects the graph.
• Both are detected by Tarjan's low-link DFS in O(V + E).
• Bridge condition: low[v] > disc[u] (strict). Articulation condition: low[v] >= disc[u] (non-strict) plus the root special case.
• For undirected graphs you do not need an onStack array; just skip the immediate parent edge.
• LeetCode 1192 (Critical Connections) is the textbook bridge-finding interview problem.
• The same machinery generalises to biconnected components and is the foundation of network-resilience analysis used in production systems.