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

Critical Connections in a Network

Master this topic with zero to advance depth.

Critical Connections in a Network

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a_i, b_i] represents a connection between servers a_i and b_i.

Any connected graph with no cycles is a tree. A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

Visual Representation

Servers: 4, Connections: [[0,1],[1,2],[2,0],[1,3]] 0---1---3 \ / 2 Removing [1,3] splits the graph. Removing [0,1], [1,2], or [2,0] doesn't split it (cycle 0-1-2). Result: [[1,3]]
Hard

Examples

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

[1,3] is the only bridge.

Approach 1

Level I: Brute Force (Edge Removal + Connectivity)

Intuition

Try removing each edge one by one and check if the graph remains connected. If it doesn't, that edge is a critical connection.

Complexity

  • Time: O(E∗(V+E))O(E * (V + E))
  • Space: O(V+E)O(V + E)
⏱ O(E * (V + E))💾 O(V + E)

Detailed Dry Run

4 nodes, edges [[0,1],[1,2],[2,0],[1,3]]. Remove [1,3]: unreachable. Critical!

java
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 (isCritical(n, connections, i)) res.add(connections.get(i));
        }
        return res;
    }
    private boolean isCritical(int n, List<List<Integer>> connections, int skip) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < connections.size(); i++) {
            if (i == skip) continue;
            List<Integer> e = connections.get(i);
            adj[e.get(0)].add(e.get(1)); adj[e.get(1)].add(e.get(0));
        }
        boolean[] vis = new boolean[n];
        return dfs(0, adj, vis) < n;
    }
    private int dfs(int u, List<Integer>[] adj, boolean[] vis) {
        vis[u] = true; int count = 1;
        for (int v : adj[u]) if (!vis[v]) count += dfs(v, adj, vis);
        return count;
    }
}
Approach 2

Level III: Optimal (Tarjan's Bridge-Finding Algorithm)

Intuition

Tarjan's algorithm uses DFS to find bridges by tracking discovery times and the lowest discovery time reachable via back-edges.

Pattern: Bridge Finding (Tarjan)

⏱ O(V + E)💾 O(V + E)

Detailed Dry Run

Graph: 0-1, 1-2, 2-0, 1-3. Bridge condition: low[v] > disc[u]. At node 1, child 3 has low[3]=3, disc[1]=1. 3 > 1 is TRUE. [1,3] is bridge.

java
class Solution {
    int timer = 0;
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<Integer>[] adj = new List[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)); }
        int[] disc = new int[n], low = new int[n];
        Arrays.fill(disc, -1);
        List<List<Integer>> bridges = new ArrayList<>();
        dfs(0, -1, adj, disc, low, bridges);
        return bridges;
    }
    private void dfs(int u, int p, List<Integer>[] adj, int[] disc, int[] low, List<List<Integer>> bridges) {
        disc[u] = low[u] = timer++;
        for (int v : adj[u]) {
            if (v == p) continue;
            if (disc[v] == -1) {
                dfs(v, u, adj, disc, low, bridges);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) bridges.add(Arrays.asList(u, v));
            } else low[u] = Math.min(low[u], disc[v]);
        }
    }
}
← Previous QuestionSwim in Rising Water
Next Question →Longest Path in a DAG