Divide Nodes Into the Maximum Number of Groups
Real-world version: Stacking Relay Masts Into TiersThe statement here is our own: the same inputs, outputs and technique.
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 from1tomholds 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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def magnificent_sets(n: int, links: list[list[int]]) -> int:public int magnificentSets(int n, int[][] links)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 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