0289MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Surplus Irrigation Link

Tracked in this browser only

Trains the technique from

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.

An irrigation block has valves labelled 1 through n. The pipes laid between them are given as pipes, where pipes[i] = [a_i, b_i] is a two-way pipe joining valve a_i to valve b_i with a_i < b_i. There are exactly n pipes, no pipe is repeated, no pipe joins a valve to itself, and water can travel between any two valves.

Because there are as many pipes as valves, the block carries one loop. A pipe is called surplus when tearing it out still lets water reach every valve and leaves no loop behind. Several pipes may qualify.

Return the surplus pipe that appears latest in pipes, written as [a_i, b_i] exactly as it was given.

Examples

Example 1

Input: pipes = [[1,3],[2,3],[1,2],[3,4]]
Output: [1,2]

Tearing out the pipe between valves 1 and 2 leaves 1-3, 2-3 and 3-4, which still reaches all four valves and holds no loop. The pipe between 1 and 3 also qualifies, but 1-2 appears later in the list.

Example 2

Input: pipes = [[1,2],[3,4],[2,3],[1,4]]
Output: [1,4]

All four pipes lie on the loop, so any one of them is surplus, and the one listed last is the pipe between valves 1 and 4.

Constraints

n == pipes.length
3 <= n <= 1000
pipes[i].length == 2
1 <= a_i < b_i <= pipes.length
a_i != b_i
No pipe is repeated.
Water can travel between any two valves.

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 surplus_link(pipes: list[list[int]]) -> list[int]:

Java

public int[] surplusLink(int[][] pipes)

The intended approach

Time O(n) up to the inverse-Ackermann factor of the mergesSpace O(n)

Keep a disjoint-set forest over the valves and walk the pipes in the order given, merging the two components a pipe joins. A pipe whose two valves already sit in one component closes the loop, and it is returned immediately because the pipes of the loop that precede it have all been merged already.

Pythonentry point: surplus_link

def surplus_link(pipes):
    # Merge the valves of each pipe in list order.  Every pipe of the loop except
    # its last occurrence merges two separate components, so the first pipe whose
    # valves already share a component is exactly the loop pipe that appears last.
    # O(n) time up to the inverse-Ackermann factor of the merges, O(n) space.
    n = len(pipes)
    parent = list(range(n + 1))

    def root(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for a, b in pipes:
        ra = root(a)
        rb = root(b)
        if ra == rb:
            return [a, b]
        parent[rb] = ra
    return []

The obvious version

Walk the pipes from last to first; for each one, rebuild the block without it and run a stack search from valve 1, returning the first pipe whose removal still reaches all n valves with n - 1 pipes.

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_surplus_link(pipes):
    n = len(pipes)
    for idx in range(n - 1, -1, -1):
        adj = {v: [] for v in range(1, n + 1)}
        for i, (a, b) in enumerate(pipes):
            if i == idx:
                continue
            adj[a].append(b)
            adj[b].append(a)
        seen = {1}
        stack = [1]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if v not in seen:
                    seen.add(v)
                    stack.append(v)
        if len(seen) == n:
            return [pipes[idx][0], pipes[idx][1]]
    return []

How this problem was checked

Reference solution executed against 8 test cases — 8 passed
2 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