1192. Critical Connections in a Network

Reference: LeetCode
Difficulty: Hard

Problem

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.

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:

Analysis

Tarjan’s Algorithm

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.

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

Comment
Junhao Wang
a software engineering cat