Water Connection Problem

Water Connection Problem looks like a plumbing puzzle, but it is really a question about chains in a directed graph. Each pipe points from one house to the next, and we follow those pointers to their ends.

The slow way first

You could, for each house, scan the whole pipe list over and over to find the next pipe in the chain. Re-scanning the list at every hop is wasteful — for long chains that becomes O(n²). We can do far better by indexing the pipes once.

The question to ask: given a house, what is the very next house its water flows to, and which houses start a chain? If we precompute those once, walking a chain is just following pointers.

The idea: index once, then walk each chain

Build three small lookups in a single pass over the pipes:

• out[a] = b — the house each pipe flows to.
• diam[a] = d — that pipe's diameter.
• indeg — the set of houses that have a pipe coming in.

A house is a tank (source) exactly when it is not in indeg but does have an outgoing pipe. From each tank, follow out from house to house until a house has no outgoing pipe — that is the tap. Along the way, keep the running minimum diameter; that bottleneck is the chain's answer.

The key insight: the at-most-one-in / at-most-one-out rule guarantees the pipes form simple, non-branching chains, so a plain while walk never loops or forks.

Walk through it

Step through the animation. Houses 1 and 2 have no incoming pipe, so they are the tanks. Starting at 1 we follow 1 → 4 → 5, taking min(60, 40) = 40. Starting at 2 we follow 2 → 3 → 6, taking min(50, 70) = 50. Each walk stops at the first house with no outgoing pipe.

Pseudocode

build out[a] = b and diam[a] = d for every pipe (a, b, d)
collect indeg = set of every house b that a pipe points to
result = []
for start in 1..n:
    if start has an incoming pipe, or has no outgoing pipe: skip
    node = start, min_d = infinity
    while node has an outgoing pipe:
        min_d = min(min_d, diam[node])
        node = out[node]
    result.append((start, node, min_d))   # node is now the tap
return result

The Python solution

def water_connection(n, pipes):
    out, diam, indeg = {}, {}, set()
    for a, b, d in pipes:
        out[a], diam[a] = b, d
        indeg.add(b)
    result = []
    for start in range(1, n + 1):
        if start in indeg or start not in out:
            continue
        node, min_d = start, float("inf")
        while node in out:
            min_d = min(min_d, diam[node])
            node = out[node]
        result.append((start, node, min_d))
    return result

• out and diam map each house to the house it flows to and that pipe's diameter.
• indeg is the set of houses with a pipe coming in — anything not in it is a potential tank.
• The skip line drops houses that either have an incoming pipe (mid-chain or tap) or no outgoing pipe (isolated house with no chain).
• The while loop is the chain walk: hop along out, shrinking min_d to the smallest diameter crossed.
• When the loop ends, node sits on a house with no outgoing pipe — the tap — so we record (start, node, min_d).

Complexity

We pass over the pipes once to index, then every house is visited at most once across all chain walks, so the total work is linear in houses plus pipes.

When this pattern shows up

Practice