Given a network of n servers and connections, find all critical connections. A critical connection is one whose removal makes some server unable to reach some other server (a bridge in graph theory).
Input: n=4, connections=[[0,1],[1,2],[2,0],[1,3]] → Output: [[1,3]]
Use Tarjan's bridge-finding algorithm with discovery time and low values. An edge (u,v) is a bridge if low[v] > disc[u].
- DFS with timer tracking disc[u] and low[u].
- low[u] = min(disc[u], disc[neighbor]) for all back edges, min(low[child]) for tree edges.
- For each tree edge (u,v): if low[v] > disc[u], it is a bridge.
- Collect all bridges.
import java.util.*;
class Solution {
int timer = 0;
int[] disc, low;
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
disc = new int[n]; low = new int[n];
Arrays.fill(disc, -1);
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
for (List<Integer> c : connections) { graph.get(c.get(0)).add(c.get(1)); graph.get(c.get(1)).add(c.get(0)); }
for (int i = 0; i < n; i++) if (disc[i] == -1) dfs(graph, i, -1);
return res;
}
private void dfs(List<List<Integer>> graph, int u, int parent) {
disc[u] = low[u] = timer++;
for (int v : graph.get(u)) {
if (v == parent) continue;
if (disc[v] == -1) {
dfs(graph, v, u);
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]);
}
}
}
- Time Complexity: O(V+E)
- Space Complexity: O(V+E)