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.

Solution:

Targan's algo

Time: O(E + V)

class Solution {
    private Map<Integer, Set<Integer>> buildGraph(List<List<Integer>> connections) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (List<Integer> conn : connections) {
            int start = conn.get(0);
            int end = conn.get(1);
            Set<Integer> neis = graph.getOrDefault(start, new HashSet<>());
            neis.add(end);
            graph.put(start, neis);
            neis = graph.getOrDefault(end, new HashSet<>());
            neis.add(start);
            graph.put(end, neis);
        }
        return graph;
    }
    
    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        Map<Integer, Set<Integer>> graph = buildGraph(connections);
        List<List<Integer>> result = new ArrayList<>();
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        int[] dfn = new int[n];
        int[] low = new int[n];
        for (int i = 0; i < n; i ++) {
            if (dfn[i] == 0) {
                dfs(i, parent, dfn, low, result, 1, graph);
            }
        }
        return result;
    }
    
    private void dfs(int x, int[] parent, int[] dfn, int[] low, List<List<Integer>> result, int depth, Map<Integer, Set<Integer>> graph) {
        dfn[x] = depth;
        low[x] = depth;
        for (int y : graph.get(x)) {
            if (dfn[y] == 0) {
                parent[y] = x;
                dfs(y, parent, dfn, low, result, depth + 1, graph);
                if (low[y] > dfn[x]) {
                    result.add(Arrays.asList(x, y));
                }
                low[x] = Math.min(low[x], low[y]);
            } else if (y != parent[x]) {
                low[x] = Math.min(low[x], dfn[y]);
            }
        }
    }
}