[LC] 1192. 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, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some server unable to reach some other server.

Return all critical connections in the network in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Constraints:

• 1 <= n <= 10^5
• n-1 <= connections.length <= 10^5
• connections[i][0] != connections[i][1]
• There are no repeated connections.

class Solution {
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer>[] graph = new ArrayList[n];
        int[] jumps = new int[n];
        Arrays.fill(jumps, -1);
        // build bidirectional graph
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (List<Integer> list : connections) {
            int from = list.get(0);
            int to = list.get(1);
            graph[from].add(to);
            graph[to].add(from);
        }
        
        dfs(0, -1, 0, res, graph, jumps);
        return res;
    }
    
    private int dfs(int cur, int parent, int level, List<List<Integer>> res, List<Integer>[] graph, int[] jumps) {
        jumps[cur] = level + 1;
        for (int child : graph[cur]) {
            // child == parent instead of cur
            if (child == parent) {
                continue;
            } else if (jumps[child] == -1) {
                jumps[cur] = Math.min(jumps[cur], dfs(child, cur, level + 1, res, graph, jumps));
            } else {
                jumps[cur] = Math.min(jumps[cur], jumps[child]);
            }
        }
        if (jumps[cur] == level + 1 && cur != 0) {
            res.add(Arrays.asList(parent, cur));
        }
        return jumps[cur];
    }
    
}