Formatted question description: https://leetcode.ca/all/1192.html

# 1192. Critical Connections in a Network

## Level

Hard

## Description

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

Use Tarjan algorithm. Maintain two arrays `times`

and `roots`

that stores the timesteps each node is met and the timesteps of the root of each connected component. Do depth first search starting from node 0.

Each time a new node is met, update the node’s `times`

and `roots`

value as the current timestep, and increase the timestep by 1. For each adjacent node of the current node, if it has not been visited, do depth first search from the adjacent node and update the current node’s `roots`

value, and if the adjacent node’s `roots`

value is greater than the current node’s `times`

value, the connection of the current node and the adjacent node is a critical connection, so add it to the list of critical connections. Otherwise, update the current node’s `roots`

value using the adjacent node’s `times`

value (keeping the minimum).

Finally, return the critical connections.

```
class Solution {
int[] times;
int[] roots;
int time;
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
times = new int[n];
roots = new int[n];
time = 0;
Arrays.fill(times, -1);
Arrays.fill(roots, -1);
Map<Integer, List<Integer>> edgesMap = new HashMap<Integer, List<Integer>>();
for (List<Integer> connection : connections) {
int node1 = connection.get(0), node2 = connection.get(1);
List<Integer> list1 = edgesMap.getOrDefault(node1, new ArrayList<Integer>());
List<Integer> list2 = edgesMap.getOrDefault(node2, new ArrayList<Integer>());
list1.add(node2);
list2.add(node1);
edgesMap.put(node1, list1);
edgesMap.put(node2, list2);
}
List<List<Integer>> criticalConnections = new ArrayList<List<Integer>>();
depthFirstSearch(edgesMap, 0, criticalConnections, -1);
return criticalConnections;
}
public void depthFirstSearch(Map<Integer, List<Integer>> edgesMap, int node, List<List<Integer>> criticalConnections, int parent) {
times[node] = time;
roots[node] = time;
time++;
List<Integer> adjacentList = edgesMap.getOrDefault(node, new ArrayList<Integer>());
for (int adjacentNode : adjacentList) {
if (adjacentNode == parent)
continue;
if (times[adjacentNode] == -1) {
depthFirstSearch(edgesMap, adjacentNode, criticalConnections, node);
roots[node] = Math.min(roots[node], roots[adjacentNode]);
if (roots[adjacentNode] > times[node])
criticalConnections.add(Arrays.asList(node, adjacentNode));
} else
roots[node] = Math.min(roots[node], times[adjacentNode]);
}
}
}
```