1014MediumDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Does the Cabling Form a Single Tree

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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

Python

def valid_tree(n: int, links: list[list[int]]) -> bool:

Java

public boolean validTree(int n, int[][] links)

The intended approach

Time O(n + m) near enough, for n cabinets and m links.Space O(n) for the representatives and group sizes.

A tree over `n` cabinets always has exactly one link fewer than it has cabinets, so check the count first; anything else and the answer is no. With the count right, being all-reachable and being loop-free stop being two questions and become one, so testing either settles the matter. Take the links one at a time, keeping a representative per group of already-joined cabinets. For a link, look up the representatives of both ends. Ends that already share one mean the link closes a loop, so answer no. Otherwise merge the two groups. Surviving every link means no loop was ever closed, and one fewer merge than there are cabinets, none of them wasted, must leave a single group holding all of them. Hanging the smaller group under the larger and flattening the chains while walking them keeps every lookup near constant.

Pythonentry point: valid_tree

def valid_tree(n, links):
    if len(links) != n - 1:
        return False
    parent = list(range(n))
    size = [1] * n
    def top(x):
        root = x
        while parent[root] != root:
            root = parent[root]
        while parent[x] != root:
            parent[x], x = root, parent[x]
        return root
    for pair in links:
        a = top(pair[0])
        b = top(pair[1])
        if a == b:
            return False
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    return True

The obvious version

Build the neighbour lists, then walk out from cabinet 0 with a queue, remembering which link each cabinet was reached by. Reaching a cabinet that has already been reached, by any link other than the one it came in on, closes a loop. At the end every cabinet must have been reached. Uses a walk and neighbour lists rather than group representatives.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_valid_tree(n, links):
    from collections import deque
    near = [[] for _ in range(n)]
    for at, pair in enumerate(links):
        near[pair[0]].append((pair[1], at))
        near[pair[1]].append((pair[0], at))
    seen = [False] * n
    seen[0] = True
    queue = deque([(0, -1)])
    reached = 1
    while queue:
        here, came = queue.popleft()
        for there, which in near[here]:
            if which == came:
                continue
            if seen[there]:
                return False
            seen[there] = True
            reached += 1
            queue.append((there, which))
    return reached == n

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in