359. Water Connection Problem

A village has n houses numbered 1 to n. p pipes are given as (a, b, d), meaning water flows from house a to house b through a pipe of diameter d. Every house has at most one outgoing pipe and at most one incoming pipe, so the pipes form simple non-branching chains. A house with an outgoing pipe but no incoming pipe is a tank (a chain's start); a house with an incoming pipe but no outgoing pipe is a tap (a chain's end). For every chain, find its tank, its tap, and the minimum diameter along the whole chain (the bottleneck that limits its flow). Print the number of chains, then one line per chain as 'tank tap minDiameter', ordered by increasing tank number.

Input: The first line contains an integer n, the number of houses. The second line contains an integer p, the number of pipes. Each of the next p lines contains three space-separated integers a, b, and d, meaning a pipe of diameter d from house a to house b. Output: Print the number of chains, then one line per chain as 'tank tap minDiameter', ordered by increasing tank number.

1 <= n <= 10^4, 0 <= p < n

Since every house has AT MOST one outgoing and one incoming pipe (the problem guarantees this), the whole pipe network genuinely forms simple, non-branching chains - this guarantee is exactly what makes the 'walk forward from each start' approach clean and unambiguous.

Given houses connected by pipes forming non-branching chains, find each chain's start (tank), end (tap), and the minimum pipe diameter along it. Brute force: For every house, try to trace a chain starting from it and check for consistency - this redundantly re-explores the SAME chain multiple times (once from each of its member houses) unless you specifically identify true chain STARTS first. Optimised: Identifying true chain STARTS upfront (houses with an outgoing pipe but no incoming one) ensures each chain is walked exactly ONCE, from its genuine beginning - tracking the minimum diameter as a simple running value during this single walk avoids any redundant re-tracing.

First identify every house that has an outgoing pipe but no incoming pipe (a tank). Then, for each such tank, repeatedly follow its chain by searching through the entire list of p pipes each time to find the pipe whose start matches the current house, tracking the minimum diameter seen and moving to the next house, until no pipe starts at the current house (a tap). This correctly follows each chain to completion, but re-scanning all p pipes at every single step of every chain makes it slow when chains are long. Time: O(n * p) Space: O(n)

Build a hashmap from each house to its outgoing (nextHouse, diameter) pair, and a set of houses that have an incoming pipe. Identify tanks as houses with an outgoing pipe but not present in the incoming set, then for each tank follow the chain via O(1) hashmap lookups instead of scanning all pipes, tracking the running minimum diameter until reaching a house with no outgoing entry (the tap). This is a large improvement over the brute approach because each step of the chain is now a constant-time lookup rather than a linear scan. Time: O(n + p) Space: O(n)

Since houses are numbered 1 to n, use plain arrays instead of hashmaps: an outHouse[] and outDiameter[] array for each house's outgoing pipe, and a hasIncoming[] boolean array. Iterate house numbers from 1 to n in order; whenever a house has an outgoing pipe and no incoming pipe, it is a tank, so follow the chain via direct array indexing (which has less overhead than hashmap lookups) tracking the minimum diameter until reaching a house with no outgoing pipe. Because tanks are discovered in increasing house-number order during this single pass, the chains come out already sorted by tank number with no extra sorting step needed, giving the tightest constant factors of the three approaches. Time: O(n + p) Space: O(n)

1. A house is a chain's START (a 'tank') if it has an outgoing pipe but never appears as anyone's incoming pipe destination. 2. From each such start, walk FORWARD along outgoing pipes until reaching a house with no outgoing pipe (the chain's 'tap'), tracking the MINIMUM diameter seen along the way. 3. Sort the resulting chains by their starting house number before printing.

Time: O(n + p) - identifying starts takes one pass over the pipes, and walking all chains combined visits each pipe exactly once total. Space: O(n), for tracking each house's outgoing pipe destination and diameter, plus a marker for which houses are pipe destinations.

p = 0 (no chains at all), a house that is neither a source nor a destination of any pipe, and n at its maximum of 10^4 to confirm the chain-walking approach runs efficiently.

Be ready to explain precisely how to identify a chain's START (outgoing pipe present, but never a destination of any pipe) - this identification step is the crux of doing the whole problem in linear time instead of redundant re-tracing.