Cables Whose Loss Splits the Network
Implement criticalLinks
A data centre has n servers joined by cables (an undirected graph given as an adjacency list). A cable is critical if removing it makes some servers unable to reach each other. Find all critical cables.
Trying every cable works but repeats a full search each time. Tarjan's algorithm finds all of them in a single depth-first search by comparing discovery times with the earliest time each subtree can reach ("low-link" values).
Example 1:
Input: graph = [[1,2],[0,2,3],[0,1],[1,4,5],[3,5],[3,4,6],[5,7],[6]]
Output: [[1,3],[5,6],[6,7]]
Example 2:
Input: graph = [[1],[0,2],[1]]
Output: [[0,1],[1,2]]
Example 3:
Input: graph = [[1,2],[0,2],[0,1]]
Output: []
+ 15 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ n ≤ 8 servers numbered 0 … n-1; graph[u] lists, in increasing order, every server joined to u by a cable (adjacency-list form of an undirected graph) - ●
If v is in graph[u] then u is in graph[v]; there are no cables from a server to itself and no repeated cables - ●
The network may consist of several separate parts - ●
A cable is critical (a bridge) when removing it increases the number of separate parts. Return all critical cables as [u, v] with u < v, sorted by u and then by v
graph =
[[1,2], [0,2,3], [0,1], [1,4,5], [3,5], [3,4,6], [5,7], [6]]