Course4all

Critical Connections in a Network

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Union Find.

Critical Connections in a Network

An edge in an undirected graph is a critical connection (bridge) if removing it increases the number of connected components. Return all such edges.

Relation to DSU

While standard DSU doesn't easily find bridges (Tarjan's or Kosaraju's are preferred), we can use a specialized 2-Edge-Connected Components algorithm using DSU. Any edge that is part of a cycle is NOT critical. We can use DSU to merge nodes in the same cycle.
Hard

Examples

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Approach 1

Level II: Brute-Force DFS (Bridge Detection)

Intuition

For each connection [u,v][u, v], remove it from the graph and check if the graph is still connected using DFS. If it's not, the edge is a critical connection.
⏱ O(E \cdot (V + E)).💾 O(V + E).
java
import java.util.*;
class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < connections.size(); i++) {
            if (isBridge(n, connections, i)) res.add(connections.get(i));
        }
        return res;
    }
    private boolean isBridge(int n, List<List<Integer>> conn, int skip) {
        List<Integer>[] adj = new List[n]; for (int i=0; i<n; i++) adj[i]=new ArrayList<>();
        for (int i=0; i<conn.size(); i++) if(i!=skip) { adj[conn.get(i).get(0)].add(conn.get(i).get(1)); adj[conn.get(i).get(1)].add(conn.get(i).get(0)); }
        boolean[] v = new boolean[n]; dfs(adj, 0, v);
        for (boolean seen : v) if (!seen) return true;
        return false;
    }
    private void dfs(List<Integer>[] adj, int u, boolean[] v) {
        v[u]=true; for(int next:adj[u]) if(!v[next]) dfs(adj, next, v);
    }
}
Approach 2

Level III: Tarjan's Algorithm (Standard)

Intuition

Use DFS discovery time and 'low-link' values. An edge (u,v)(u, v) is a bridge if low[v]>disc[u]low[v] > disc[u].
⏱ O(V + E).💾 O(V).
java
import java.util.*;
class Solution {
    List<Integer>[] adj;
    int[] disc, low;
    int timer = 0;
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        adj = new ArrayList[n];
        for(int i=0; i<n; i++) adj[i] = new ArrayList<>();
        for(List<Integer> c : connections) { adj[c.get(0)].add(c.get(1)); adj[c.get(1)].add(c.get(0)); }
        disc = new int[n]; low = new int[n]; Arrays.fill(disc, -1);
        List<List<Integer>> res = new ArrayList<>();
        dfs(0, -1, res);
        return res;
    }
    void dfs(int u, int p, List<List<Integer>> res) {
        disc[u] = low[u] = ++timer;
        for(int v : adj[u]) {
            if(v == p) continue;
            if(disc[v] == -1) {
                dfs(v, u, res);
                low[u] = Math.min(low[u], low[v]);
                if(low[v] > disc[u]) res.add(Arrays.asList(u, v));
            } else low[u] = Math.min(low[u], disc[v]);
        }
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionRedundant Connection II
Next Question →Minimum Score of a Path Between Two Cities