Show problems as
Classic problem #1192HardDepth-First SearchGraph TheoryBiconnected ComponentBridge (Graph)

Critical Connections in a Network

Real-world version: Critical Water Mains
Tracked in this browser only
Read Critical Connections in a Network on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A water utility runs stations pumping stations, numbered 0 to stations - 1, joined by two-way mains. mains[i] = [a, b] means a main runs between station a and station b. Water can travel along a main in either direction, no main joins a station to itself, and no pair of stations is joined twice. Right now every station can reach every other station through the network.

A main is critical when taking it out of service leaves at least one pair of stations with no route between them.

Return the list of critical mains. Report each one as [u, v] with u < v, and sort the returned list in ascending order, so the answer is unique.

Examples

Example 1

Input
stations = 6, mains = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]]
Output
[[1, 3]]

Stations 0, 1, 2 sit on one loop and stations 3, 4, 5 sit on another. Taking the main between 1 and 3 out of service leaves no route from station 0 to station 4. Every other main has a loop around it, so service survives without it.

Example 2

Input
stations = 4, mains = [[0, 1], [1, 2], [2, 3]]
Output
[[0, 1], [1, 2], [2, 3]]

The network is a single chain. Removing any one of the three mains cuts the chain into two pieces, so all three are critical.

Example 3

Input
stations = 5, mains = [[1, 0], [1, 2], [2, 3], [3, 1], [4, 3]]
Output
[[0, 1], [3, 4]]

Stations 1, 2, 3 form a loop, so none of those three mains is critical. Station 0 hangs off station 1 and station 4 hangs off station 3, so both of those mains are critical. Note that the input lists them as [1, 0] and [4, 3] while the answer reports them smaller endpoint first.

Example 4

Input
stations = 3, mains = [[2, 0], [0, 1], [1, 2]]
Output
[]

The three stations form one loop, so every station still has a route to the others after any single main is taken out.

Constraints

  • 2 <= stations <= 10^5
  • stations - 1 <= mains.length <= 10^5
  • mains[i].length == 2
  • 0 <= a, b <= stations - 1
  • a != b
  • No pair of stations appears twice in mains.
  • Every station can reach every other station through the mains.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def critical_mains(stations: int, mains: list[list[int]]) -> list[list[int]]:
Java
public List<List<Integer>> criticalMains(int stations, List<List<Integer>> mains)

More on the same topics