# 1192. Critical Connections in a Network

Reference: LeetCode

Difficulty: Hard

## Problem

There are

`n`

servers numbered from`0`

to`n-1`

connected byundirectedserver-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.

**Constraints:**

`1 <= n <= 10^5`

`n-1 <= connections.length <= 10^5`

`connections[i][0] != connections[i][1]`

(no self-link)- There are no repeated connections.

**Example:**

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

**Follow up:**

## Analysis

### Tarjan’s Algorithm

Reference: Java DFS Solution similar to Tarjan, maybe easier to understand

We record the timestamp that we visit each node. For each node, we check every neighbor except its parent and return a smallest timestamp in all its neighbors. If this timestamp is strictly less than the node’s timestamp, we know that this node is somehow in a cycle. Otherwise, this edge from the parent to this node is a critical connection.

1 | int T = 1; |

**Time:** $O(V + E)$ (connected graph)**Space:** $O(V + E)$