A data centre has n servers, numbered 0 .. n-1, joined by two-way cables: each [a, b] in connections is a cable between servers a and b. Right now every server can reach every other one, directly or through other servers.
A cable is critical if cutting it alone would split the network, leaving some pair of servers with no route between them.
Write critical_connections(n: int, connections: list[list[int]]) -> list[list[int]] that returns every critical cable. Return them in any order, and write each cable's two ends in either order.
Examples:
critical_connections(6, [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4], [4, 5], [5, 3]])
# [[2, 3]]
Two triangles of servers are joined by one cable, [2, 3]. Cutting any cable inside a triangle is harmless, since the traffic goes the other way round the triangle.
critical_connections(5, [[0, 1], [1, 2], [2, 3], [1, 3], [3, 4]]) # [[0, 1], [3, 4]] (any order)
critical_connections(4, [[0, 1], [1, 2], [2, 3], [3, 0]]) # [] every cable is on a loop
Constraints: 2 <= n <= 10^5, n - 1 <= len(connections) <= 10^5. The network is connected, no cable joins a server to itself, and no two cables join the same pair.
⭐ Bonus: speed tests with 50,000 servers, one of them a single long chain, earn a star in O(n + len(connections)) without deep recursion. Cutting each cable in turn and checking the network again is O(len(connections)²).
Show hint
run one depth-first search. For each server, work out the earliest-visited server that its part of the search tree can reach using a single cable that isn't a tree cable. A tree cable into a server is critical exactly when that subtree can't reach back above it.