Graph Valid Tree
Real-world version: Does the Cabling Form a Single TreeThe statement here is our own: the same inputs, outputs and technique.
A site has n cabinets numbered 0 through n - 1, joined by the two-way links links, where links[i] = [a, b] joins cabinet a and cabinet b.
Return whether the links form a single tree: every cabinet reachable from every other, and no closed loop of links anywhere.
Examples
Example 1
- Input
- n = 5, links = [[0, 1], [0, 2], [0, 3], [1, 4]]
- Output
- true
Four links join five cabinets, cabinet 0 reaches 1, 2 and 3 directly and 4 through 1, and no link ever joins two cabinets already connected.
Example 2
- Input
- n = 5, links = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
- Output
- false
Five links for five cabinets is one too many, and indeed cabinets 1, 2 and 3 sit in a closed loop.
Example 3
- Input
- n = 4, links = [[0, 1], [2, 3]]
- Output
- false
Two links leave two separate pairs of cabinets, so nothing in one pair reaches anything in the other.
Constraints
- 1 <= n <= 2000
- 0 <= links.length <= 5000
- links[i].length == 2
- 0 <= links[i][j] <= n - 1
- The two ends of a link are different cabinets.
- No pair of cabinets is linked twice.
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 valid_tree(n: int, links: list[list[int]]) -> bool:public boolean validTree(int n, int[][] links)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 18 test cases: 18 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