Show problems as
Classic problem #684MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Redundant Connection

Real-world version: Surplus Irrigation Link
Tracked in this browser only
Read Redundant Connection on LeetCode(opens in a new tab)

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

Learn the pattern firstFinding Connected Components · Graphs, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def surplus_link(pipes: list[list[int]]) -> list[int]:
Java
public int[] surplusLink(int[][] pipes)

More on the same topics