All problems

Critical Cables

Hard · graph traversal

A network has n servers numbered 0 to n - 1. They are joined by two-way cables, given as a list cables of pairs [a, b]. Every server can reach every other server through the cables.

A cable is critical if cutting that one cable on its own would leave the network split into two or more groups that can no longer reach each other.

Return every critical cable. Write each cable as [smaller, larger] (the smaller server number first), and sort the list in ascending order: by the first number, then by the second. If no cable is critical, return an empty list [].

A pair in cables may be written in either order. No two cables join the same pair of servers, and no cable joins a server to itself.

Examples

Example 1

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

Output: [[1, 3]]

Servers 0, 1 and 2 form a loop, so cutting any one of those cables still leaves them connected. Cutting [1, 3] cuts server 3 off.

Example 2

Input: n = 3, cables = [[0, 1], [1, 2], [2, 0]]

Output: []

In a loop of three, any single cable can be cut and every server can still be reached the other way round.

Example 3

Input: n = 5, cables = [[0, 1], [1, 2], [3, 2], [3, 4]]

Output: [[0, 1], [1, 2], [2, 3], [3, 4]]

The servers form a single line, so every cable is critical. The cable written [3, 2] is reported as [2, 3].

Constraints