Emergency Beacons for Orbital Outposts
Smallest node in each undirected graph component with no active node
A space mission operates n orbital outposts, numbered from 0 to n - 1. The two-way communication links are given in links, where [u, v] means outposts u and v can communicate directly.
An emergency signal can travel through any number of links. Some outposts already have an emergency beacon; their numbers are listed in active.
Every group of mutually reachable outposts must have at least one beacon. For each group that currently has no beacon, the mission will install exactly one at the smallest-numbered outpost in that group.
Return the outpost numbers where new beacons should be installed, in increasing order. An outpost with no links forms a group by itself.
Examples
Example 1
Input: n = 6, links = [[0,2],[2,4],[1,3]], active = [4] Output: [1,5]
Outposts 0, 2, and 4 form one group with an existing beacon at 4. Outposts 1 and 3 form a group without a beacon, so its smallest-numbered outpost needs one. Outpost 5 is isolated and also needs a beacon.
Example 2
Input: n = 4, links = [[2,3],[1,2],[0,3]], active = [] Output: [0]
All four outposts can reach one another, and none has a beacon. Only the smallest-numbered outpost in this group needs a new beacon.
Example 3
Input: n = 4, links = [], active = [3,1] Output: [0,2]
There are no links, so each outpost is its own group. The outposts already listed in active need no installation.
Constraints
- 1 <= n <= 20000
- 0 <= links.length <= 2500
- Each element of links contains exactly two integers u and v, with 0 <= u, v < n and u != v.
- No undirected link appears more than once; [u, v] and [v, u] represent the same link.
- 0 <= active.length <= n
- Every value in active is a distinct integer from 0 to n - 1.
An iterative traversal avoids recursion-depth limits. The reference solution runs in O(n + links.length + active.length) time and uses O(n + links.length) auxiliary space.
Hints
Show hint 1Hint 1
Outposts belong to the same group exactly when they are in the same connected component.
Show hint 2Hint 2
Traverse each component once, checking whether it contains an active beacon. Starting new traversals in increasing outpost order also identifies each component's smallest outpost.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the solution if each outpost had an installation cost, and ties between minimum-cost outposts were broken by outpost number?
- How could you maintain the number of groups still needing beacons as new communication links are added?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem