Course4all
Join us on telegram
Home/dsa/Union Find/Critical Connections in a Network

Critical Connections in a Network

Master this topic with zero to advance depth.

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]);
        }
    }
}
← Previous QuestionRedundant Connection II
Next Question →Minimum Score of a Path Between Two Cities