Find if Path Exists in Graph
Real-world version: Coolant Reaches the OutletThe statement here is our own: the same inputs, outputs and technique.
A chilled-water plant is laid out as junctions junctions, labelled 0 through junctions - 1. The plumbing is given as pipes, where pipes[i] = [a, b] is one pipe that carries coolant in either direction between junction a and junction b.
A maintenance engineer wants to know whether coolant leaving the junction intake can arrive at the junction outlet by running through a sequence of pipes, using each junction at most once along the way.
Return true if such a run of pipes exists and false otherwise. intake and outlet may refer to the same junction, in which case no pipe has to be used at all.
No pipe joins a junction to itself, and no unordered pair of junctions is listed twice, though a pair may be written in either order.
Examples
Example 1
- Input
- junctions = 4, pipes = [[0, 2], [2, 3]], intake = 0, outlet = 3
- Output
- true
Coolant can take the pipe from 0 to 2 and then the pipe from 2 to 3, arriving at the outlet.
Example 2
- Input
- junctions = 5, pipes = [[0, 1], [1, 2], [3, 4]], intake = 2, outlet = 4
- Output
- false
Every pipe out of 2 leads to 1 or 0, and no pipe is listed from 0, 1 or 2 to either 3 or 4, so the outlet is never reached.
Example 3
- Input
- junctions = 4, pipes = [[1, 0], [2, 1], [3, 2]], intake = 0, outlet = 3
- Output
- true
The pipes [1, 0], [2, 1] and [3, 2] carry coolant in either direction, so the run 0, 1, 2, 3 is available.
Constraints
- 1 <= junctions <= 2 * 10^5
- 0 <= pipes.length <= 2 * 10^5
- pipes[i].length == 2
- 0 <= a, b <= junctions - 1
- a != b
- 0 <= intake, outlet <= junctions - 1
- No unordered pair of junctions appears in pipes more than once
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.
def coolant_reaches(junctions: int, pipes: list[list[int]], intake: int, outlet: int) -> bool:public boolean coolantReaches(int junctions, int[][] pipes, int intake, int outlet)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's