The pneumatic post

A hospital moves blood samples between wards in plastic carriers, blown through tubes. Maintenance wants the list of tubes that no ward can afford to lose.

The problem

The network has stations stations, numbered 0 to stations - 1, joined by two-way tubes. A carrier can travel from any station to any other, hopping through intermediate stations as needed.

A tube is critical if sealing it would leave at least one pair of stations with no route between them at all. Report every critical tube. Order does not matter, and each tube may be reported with its two stations in either order.

Input. stations — an integer, the number of stations. tubes — a list of [a, b] pairs, each a two-way tube.

Output. A list of the critical tubes, each as a pair of station numbers.

Example.

stations = 4, tubes = [[0,1], [1,2], [2,0], [1,3]]  ->  [[1,3]]

Stations 0, 1 and 2 sit on a loop, so any one tube of that loop can be sealed and carriers reroute the other way round. Station 3 hangs off station 1 by a single tube, so that tube is the only critical one.

Example.

stations = 6, tubes = [[0,1], [1,2], [2,0], [3,4], [4,5], [5,3], [2,3]]  ->  [[2,3]]

Two loops joined by one tube. Seal [2,3] and the two wings cannot reach each other; seal anything else and both loops still hold together.

Constraints.

• 2 <= stations <= 10^5
• stations - 1 <= len(tubes) <= 10^5
• 0 <= a, b < stations and a != b
• No pair appears twice; the network is connected.

Hints

Approach

Brute force

Seal one tube, run a traversal, check whether every station is still reachable, put the tube back. One O(V + E) sweep per tube: 10⁵ tubes times 2 × 10⁵ steps is 2 × 10¹⁰ operations. Correct and far too slow.

The insight

A tube is critical exactly when the subtree hanging below it has no back tube reaching above it, and one depth-first walk measures that for every tube at once.

Stamp each station with entered, its position in the walk order, and compute reach: the smallest entered value the station or anything below it can touch without re-using the tube it arrived on. A back tube to an older station pulls reach down; a child passes its reach up to its parent. The tube from parent to child is critical precisely when reach[child] > entered[parent], because then every route out of the child's subtree runs back through it. In an undirected graph every non-tree tube leads to an ancestor, which is why one number per station is enough.

Algorithm

1. Build adjacency lists holding (neighbour, tube_id).
2. Walk depth-first from station 0, stamping entered and reach on entry.
3. Skip the exact tube you arrived on — by id, not by neighbour.
4. Meeting an already-stamped station, pull reach[station] down to its entered value.
5. Finishing a child, pull the parent's reach down to the child's, and record the tube when reach[child] > entered[parent].

Complexity

Time O(V + E) — one walk, each tube looked at twice. Space O(V + E) for the adjacency lists and the explicit stack.

Solution

"""The pneumatic post — bridges of an undirected graph by iterative low-link search."""


def solve(stations, tubes):
    links = [[] for _ in range(stations)]
    for tube_id, (a, b) in enumerate(tubes):
        links[a].append((b, tube_id))
        links[b].append((a, tube_id))

    entered = [-1] * stations          # visit order, -1 while unvisited
    reach = [0] * stations             # earliest entry time reachable without the parent tube
    clock = 0
    critical = []

    for root in range(stations):
        if entered[root] != -1:
            continue
        entered[root] = reach[root] = clock
        clock += 1
        # frame: (station, tube we arrived on, index of the next neighbour to try)
        stack = [(root, -1, 0)]
        while stack:
            station, arrived_on, k = stack.pop()
            if k < len(links[station]):
                stack.append((station, arrived_on, k + 1))
                nxt, tube_id = links[station][k]
                if tube_id == arrived_on:
                    continue           # never walk back along the tube we came in on
                if entered[nxt] == -1:
                    entered[nxt] = reach[nxt] = clock
                    clock += 1
                    stack.append((nxt, tube_id, 0))
                elif entered[nxt] < reach[station]:
                    reach[station] = entered[nxt]   # a back tube to an older station
            elif stack:
                parent = stack[-1][0]
                if reach[station] < reach[parent]:
                    reach[parent] = reach[station]
                # invariant: the subtree below `station` reaches no further back
                # than reach[station]; if that misses the parent, the tube is a bridge
                if reach[station] > entered[parent]:
                    critical.append([parent, station] if parent < station else [station, parent])

    critical.sort()
    return critical

TESTS = [
    # One loop of three chambers plus a spur: only the spur is critical.
    ((4, [[0, 1], [1, 2], [2, 0], [1, 3]]), [[1, 3]]),
    # Two loops hinged on a single tube: that hinge is the only bridge.
    ((6, [[0, 1], [1, 2], [2, 0], [3, 4], [4, 5], [5, 3], [2, 3]]), [[2, 3]]),
    # A plain chain: every tube is critical.
    ((4, [[0, 1], [1, 2], [2, 3]]), [[0, 1], [1, 2], [2, 3]]),
    # A single loop has no critical tube at all.
    ((3, [[0, 1], [1, 2], [2, 0]]), []),
    # Two stations, one tube.
    ((2, [[0, 1]]), [[0, 1]]),
    # A long chain, deeper than a recursive search would survive.
    ((5000, [[i, i + 1] for i in range(4999)]), [[i, i + 1] for i in range(4999)]),
]

Pitfalls

• Skipping the parent by station number instead of by tube id. With two tubes between the same pair, both get skipped and both are wrongly reported critical. Skip the arriving tube's id.
• Comparing against reach[parent] instead of entered[parent]. The parent may already have been pulled down by a sibling's back tube, and the test then misses real bridges.
• Recursing. A chain of 10⁵ stations is 10⁵ frames deep and the interpreter stops near 1,000. Keep an explicit stack.

Variants

• Two cabinets — the same single walk, carrying a colour outward instead of a low-link number back up.
• BFS and DFS — the traversal this is built on, and why the walk order is what makes the trick work.