0309HardDepth-First SearchGraph TheoryBiconnected ComponentBridge (Graph)

Critical Water Mains

Tracked in this browser only

Trains the technique from

LeetCode 1192Critical Connections in a Network

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n + m + b log b), where b is the number of critical mains returnedSpace O(n + m)

Run one depth-first search over the network, stamping each station with the time it was first entered and tracking, for each station, the earliest stamp reachable from its search subtree using any single non-tree main. A tree main from `parent` to `node` is critical exactly when nothing in `node`'s subtree can reach a stamp at or before `parent`'s own stamp. The search is driven by an explicit stack of stored iterators so the depth of the network never matters, and the collected pairs are normalised smaller endpoint first and sorted before returning.

Pythonentry point: critical_mains

def critical_mains(stations, mains):
    # Iterative depth-first search, so a 10^5-station network cannot blow the stack.
    # O(n + m) for the search plus O(b log b) to sort the b critical mains.
    # O(n + m) space for the adjacency lists and the search bookkeeping.
    adj = [[] for _ in range(stations)]
    for idx in range(len(mains)):
        a = mains[idx][0]
        b = mains[idx][1]
        adj[a].append((b, idx))
        adj[b].append((a, idx))
    disc = [-1] * stations
    low = [0] * stations
    timer = 0
    found = []
    for root in range(stations):
        if disc[root] != -1:
            continue
        disc[root] = low[root] = timer
        timer += 1
        stack = [(root, -1, iter(adj[root]))]
        while stack:
            node, via, walker = stack[-1]
            descended = False
            for nxt, eid in walker:
                if eid == via:
                    continue
                if disc[nxt] == -1:
                    disc[nxt] = low[nxt] = timer
                    timer += 1
                    stack.append((nxt, eid, iter(adj[nxt])))
                    descended = True
                    break
                if disc[nxt] < low[node]:
                    low[node] = disc[nxt]
            if descended:
                continue
            stack.pop()
            if stack:
                parent = stack[-1][0]
                if low[node] < low[parent]:
                    low[parent] = low[node]
                if low[node] > disc[parent]:
                    a = mains[via][0]
                    b = mains[via][1]
                    found.append([a, b] if a < b else [b, a])
    found.sort()
    return found

The obvious version

Take each main out of service one at a time, flood the remaining network from station 0, and keep the main if some station is no longer reachable.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_critical_mains(stations, mains):
    out = []
    for skip in range(len(mains)):
        adj = [[] for _ in range(stations)]
        for idx in range(len(mains)):
            if idx == skip:
                continue
            a = mains[idx][0]
            b = mains[idx][1]
            adj[a].append(b)
            adj[b].append(a)
        seen = [False] * stations
        seen[0] = True
        reached = 1
        stack = [0]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    reached += 1
                    stack.append(v)
        if reached < stations:
            a = mains[skip][0]
            b = mains[skip][1]
            out.append([a, b] if a < b else [b, a])
    out.sort()
    return out

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in