Critical Connections in a Network

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).

Example 1

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

Solution Approach

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.

Java

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)