hardGraphsPure DSA~42 min
Critical Service Links
Services form a network where each connection is bidirectional. A link is 'critical' if removing it disconnects some services from others. Find every critical link so you can prioritise redundancy.
Problem
There are n services labelled 0..n−1 and a list of undirected connections. A connection is critical (a bridge) if removing it increases the number of connected components. Return all critical connections in any order.
Input
An integer n (1 ≤ n ≤ 10^5) and connections (length up to 10^5) of [u, v] pairs.
Output
A list of the critical [u, v] connections.
Constraints
- The graph is connected and has no parallel edges or self-loops
- A bridge is an edge in no cycle
- Up to 10^5 nodes and edges
Examples
Example 1
Input
n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output
[[1,3]]
0-1-2 form a cycle (no bridges); only 1-3 is critical.
Example 2
Input
n = 2, connections = [[0,1]]
Output
[[0,1]]
The single edge is the only link, hence critical.