☕ DSA Java Articles

Topics › Graphs › Other Algorithms

Bridges in graph

Hard TUF ID 497 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with n vertices numbered 0 to n - 1 and a list of edges connections. An edge is a bridge (LeetCode calls it a critical connection) if removing it disconnects two vertices that were connected before. Return all bridges, in any order.

Constraints (LeetCode): 2 ≤ n ≤ 10^5, n - 1 ≤ connections.length ≤ 10^5, no self-loops, no repeated edges. The LeetCode graph is connected; the code below also works when it is not.

Example 1

n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
answer = [[1,3]]          // 0-1-2 is a triangle; 3 hangs off 1 by a single edge

Example 2

n = 6, connections = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5],[5,3]]
answer = [[2,3]]          // two triangles joined by one edge

A useful fact before we start: an edge is a bridge exactly when it lies on no cycle. If u-v is on a cycle, the rest of the cycle is a detour from u to v, so removing the edge disconnects nothing. If it is on no cycle, the only route from u to v is the edge itself.

Approach 1: Brute force, remove each edge and test

Intuition. Apply the definition literally. Remove one edge u-v, then ask whether u can still reach v. If not, the edge was the only connection between their sides, so it is a bridge. Removing an edge can only disconnect its own two endpoints from each other (any other pair that loses its path must have used u-v, and then it splits along the same cut), so checking u against v is enough.

Algorithm.

  1. For each edge index skip: build the adjacency list from every edge except skip.
  2. Run DFS from u and check whether it reaches v.
  3. If not, record [u, v] as a bridge.
static List<List<Integer>> bruteForce(int n, int[][] connections) {
    List<List<Integer>> bridges = new ArrayList<>();
    for (int skip = 0; skip < connections.length; skip++) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int e = 0; e < connections.length; e++) {
            if (e == skip) continue;                         // graph without edge 'skip'
            adj.get(connections[e][0]).add(connections[e][1]);
            adj.get(connections[e][1]).add(connections[e][0]);
        }
        int u = connections[skip][0], v = connections[skip][1];
        if (!reachable(adj, u, v)) bridges.add(List.of(u, v));
    }
    return bridges;
}

static boolean reachable(List<List<Integer>> adj, int src, int dst) {
    boolean[] seen = new boolean[adj.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    seen[src] = true;
    stack.push(src);
    while (!stack.isEmpty()) {
        int x = stack.pop();
        if (x == dst) return true;
        for (int y : adj.get(x)) {
            if (!seen[y]) {
                seen[y] = true;
                stack.push(y);
            }
        }
    }
    return false;
}

Complexity. Time O(E · (V + E)): for each of the E edges we rebuild the graph and run a traversal. Space O(V + E). With 10^5 edges that is around 10^10 steps, far too slow; we need one traversal that judges every edge at once.

Intuition. Run a single DFS. It turns the graph into a DFS tree plus back edges, and in an undirected graph every non-tree edge connects a vertex to one of its ancestors. A back edge closes a cycle with the tree path between its endpoints, so back edges are never bridges, and only tree edges can be.

Now look at a tree edge u → v (u is the parent). Removing it cuts off the whole DFS subtree of v. The subtree stays connected to the rest of the graph only if some vertex in it has a back edge that climbs to u or above. So we record two numbers per vertex:

Then the test is a single comparison: u-v is a bridge exactly when low[v] > tin[u]. If low[v] ≤ tin[u], something in v’s subtree reaches u or an ancestor of u by another route, which forms a cycle through u-v. If low[v] > tin[u], the subtree’s best escape is strictly below u, so it is attached only through u-v.

How low is computed. Initialise low[u] = tin[u]. Then, for each neighbour v of u:

Algorithm.

  1. Build the adjacency list. Start a DFS from every unvisited vertex (covers disconnected graphs).
  2. In dfs(u, parent): assign tin[u] = low[u] = timer++, then process neighbours as described above.
  3. After returning from child v, if low[v] > tin[u], add [u, v] to the answer.
static List<List<Integer>> tarjan(int n, int[][] connections) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : connections) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);
    }
    int[] tin = new int[n], low = new int[n], timer = new int[1];
    boolean[] visited = new boolean[n];
    List<List<Integer>> bridges = new ArrayList<>();
    for (int s = 0; s < n; s++) {
        if (!visited[s]) dfs(s, -1, adj, visited, tin, low, timer, bridges);   // every component
    }
    return bridges;
}

static void dfs(int u, int parent, List<List<Integer>> adj, boolean[] visited,
                int[] tin, int[] low, int[] timer, List<List<Integer>> bridges) {
    visited[u] = true;
    tin[u] = low[u] = timer[0]++;
    for (int v : adj.get(u)) {
        if (v == parent) continue;                           // do not walk back along the tree edge
        if (!visited[v]) {
            dfs(v, u, adj, visited, tin, low, timer, bridges);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] > tin[u]) bridges.add(List.of(u, v)); // v's subtree cannot reach u or above
        } else {
            low[u] = Math.min(low[u], tin[v]);               // back edge to an ancestor
        }
    }
}

Dry run on example 1. Adjacency: 0: [1, 2], 1: [0, 2, 3], 2: [1, 0], 3: [1].

step event tin / low updates
1 visit 0 tin0 = low0 = 0
2 tree edge 0 → 1 tin1 = low1 = 1
3 tree edge 1 → 2 tin2 = low2 = 2
4 2 sees 0 (visited, not parent) low2 = min(2, tin0) = 0
5 back at 1 from 2 low1 = min(1, 0) = 0; test low2 = 0 > tin1 = 1? no
6 tree edge 1 → 3 tin3 = low3 = 3; 3’s only neighbour is its parent
7 back at 1 from 3 test low3 = 3 > tin1 = 1? yes, bridge 1-3
8 back at 0 from 1 low0 = 0; test low1 = 0 > tin0 = 0? no

The back edge 2-0 gives the whole triangle low = 0, so none of its edges is a bridge; vertex 3 has no back edge, so its tree edge is.

Complexity. Time O(V + E): one DFS, constant work per edge endpoint. Space O(V + E) for the adjacency list plus O(V) for tin, low, visited and the recursion stack.

Edge cases and pitfalls