1090HardDepth-First SearchBreadth-First SearchUnion-FindGraph Theory

Stacking Relay Masts Into Tiers

Tracked in this browser only

Trains the technique from

LeetCode 2493Divide Nodes Into the Maximum Number of Groups

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.

There are n relay masts numbered 1 through n. links[i] = [a, b] says masts a and b talk to each other directly. No mast links to itself and at most one link joins any pair of masts.

Every mast has to be placed on a tier. Tiers are numbered 1, 2, 3, ... and the rules are:

Each mast sits on exactly one tier.
Two masts that talk directly must sit on tiers exactly one apart.
If the highest tier used is m, then every tier from 1 to m holds at least one mast.

Return the largest m any legal placement can reach, or -1 when no legal placement exists.

Examples

Example 1

Input: n = 3, links = [[1, 2], [1, 3]]
Output: 3

Put mast 2 on tier 1, mast 1 on tier 2 and mast 3 on tier 3. Both links join masts one tier apart and all three tiers are occupied.

Example 2

Input: n = 5, links = [[1, 2], [1, 3], [2, 4], [3, 5], [4, 5]]
Output: -1

The links form the ring 1, 2, 4, 5, 3 and back to 1. Each step of a ring shifts the tier by one, so a ring of five steps could never return to the tier it started on.

Example 3

Input: n = 6, links = [[1, 2], [3, 4], [5, 6]]
Output: 6

The three pairs share no links, so each pair can take a fresh pair of tiers: 1 and 2, then 3 and 4, then 5 and 6.

Constraints

1 <= n <= 500
1 <= links.length <= 10^4
links[i].length == 2
1 <= links[i][0] <= n
1 <= links[i][1] <= n
the two masts on a link are never the same
at most one link joins any pair of masts

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 magnificent_sets(n: int, links: list[list[int]]) -> int:

Java

public int magnificentSets(int n, int[][] links)

The intended approach

Time O(n * (n + m)) for a walk from every mast.Space O(n + m) for the link lists and the walk bookkeeping.

The tier rule says a link always steps the tier number by exactly one, so along any chain of links the tier goes up or down by one at every step. Walk a loop of links and the ups must cancel the downs, which means every loop has an even number of links. So a part of the network that holds a loop of odd length can never be placed, and the answer is `-1`. Two-colouring each part while walking it catches exactly that: a link joining two masts of the same colour is an odd loop. When a part does two-colour, fix any mast in it on tier one. Every other mast's tier is then forced to be one more than its distance from that mast, because a shortest chain of links can only step up one tier at a time and nothing can be reached sooner. So starting from a chosen mast the part uses exactly as many tiers as the largest distance plus one, and that placement is always legal: neighbouring masts sit at distances differing by exactly one, since equal distances would spell an odd loop. Trying every mast of the part as the starting one and keeping the deepest walk gives the most tiers that part can span. Different parts share no links, so each part can be slid up to begin just above the previous part's top tier, and every tier in between stays occupied. That makes the answer the sum of the per-part bests.

Pythonentry point: magnificent_sets

def magnificent_sets(n, links):
    from collections import deque
    adj = [[] for _ in range(n + 1)]
    for link in links:
        adj[link[0]].append(link[1])
        adj[link[1]].append(link[0])
    shade = [0] * (n + 1)
    part = [-1] * (n + 1)
    parts = []
    for seed in range(1, n + 1):
        if part[seed] != -1:
            continue
        tag = len(parts)
        members = []
        part[seed] = tag
        shade[seed] = 1
        queue = deque([seed])
        while queue:
            node = queue.popleft()
            members.append(node)
            for nb in adj[node]:
                if part[nb] == -1:
                    part[nb] = tag
                    shade[nb] = -shade[node]
                    queue.append(nb)
                elif shade[nb] == shade[node]:
                    return -1
        parts.append(members)
    total = 0
    for members in parts:
        best = 0
        for src in members:
            depth = [0] * (n + 1)
            depth[src] = 1
            far = 1
            queue = deque([src])
            while queue:
                node = queue.popleft()
                for nb in adj[node]:
                    if depth[nb] == 0:
                        depth[nb] = depth[node] + 1
                        if depth[nb] > far:
                            far = depth[nb]
                        queue.append(nb)
            if far > best:
                best = far
        total += best
    return total

The obvious version

Hand out tiers by trying every number from one to the mast count for every mast in turn, backing out as soon as a mast clashes with an already placed neighbour. When all masts hold a tier, check that no tier below the top one is empty and keep the highest top seen. The search branches over the mast count to the power of the mast count, so only small networks survive.

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_magnificent_sets(n, links):
    adj = [[] for _ in range(n + 1)]
    for link in links:
        adj[link[0]].append(link[1])
        adj[link[1]].append(link[0])
    tier = [0] * (n + 1)
    state = {"best": -1}

    def place(node):
        if node > n:
            top = 0
            for i in range(1, n + 1):
                if tier[i] > top:
                    top = tier[i]
            filled = [False] * (top + 1)
            for i in range(1, n + 1):
                filled[tier[i]] = True
            for level in range(1, top + 1):
                if not filled[level]:
                    return
            if top > state["best"]:
                state["best"] = top
            return
        for value in range(1, n + 1):
            ok = True
            for nb in adj[node]:
                if tier[nb] == 0:
                    continue
                gap = value - tier[nb]
                if gap != 1 and gap != -1:
                    ok = False
                    break
            if ok:
                tier[node] = value
                place(node + 1)
                tier[node] = 0

    place(1)
    return state["best"]

How this problem was checked

Reference solution executed against 15 test cases — 15 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