79. Critical Connections in a Network

Hard · Graph

You are given a network of `n` servers numbered from `0` to `n-1` and a list of undirected connections, where `connections[i] = [a, b]` means there is a connection between servers `a` and `b`. A **critical connection** (also called a **bridge**) is a connection that, if removed, will make some servers unable to reach other servers.

Return all critical connections in the network. Each connection in the result should be represented as a pair `[u, v]` where `u < v`. The result should be sorted: each inner pair in ascending order, and the outer list in lexicographic order.

The input is `[n, connections]` where `n` is the number of servers and `connections` is the list of edges.

Examples

Example 1
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: The connection [1,3] is the only bridge. Removing it disconnects server 3 from the rest of the network. The cycle 0-1-2-0 means none of those edges are bridges.
Example 2
Input: n = 2, connections = [[0,1]]
Output: [[0,1]]
Explanation: With only two servers and one connection, removing [0,1] disconnects the entire network, so it is a critical connection.

Constraints