A data centre has n servers, numbered 0 to n - 1, wired with one-way links. A link [u, v] lets a signal travel from u to v (not back). You may activate some servers directly; a signal then spreads from every activated server along the links, and a server that receives it passes it on.
Pick as few servers as possible so that every server ends up with the signal.
Unlike the acyclic version of this puzzle, the links may form cycles, so "servers nobody links to" is not enough: in a ring of servers every server has an incoming link, yet one of them must still be activated.
The smallest set is usually not unique, so return a canonical one: among all smallest sets, return the one whose sorted list is lexicographically smallest.
Write min_activations(n: int, edges: list[list[int]]) -> list[int] returning that set as a sorted list.
min_activations(5, [[0, 1], [1, 2], [2, 0], [3, 2], [3, 4]])
# [3] 3 reaches 2, then the ring 2 -> 0 -> 1, and 4
min_activations(6, [[1, 2], [2, 1], [3, 4], [4, 5], [5, 3], [5, 1]])
# [0, 3] 0 is isolated; the ring {3, 4, 5} feeds the ring {1, 2}
min_activations(3, [])
# [0, 1, 2]
Details:
1 <= n <= 100,000,0 <= len(edges) <= 200,000,0 <= u, v < n.- Edges may repeat, and self-loops
[v, v]may appear (they change nothing). - Recursion 100,000 levels deep will overflow Python's stack: write your graph search iteratively.
Show hint
Group servers that can reach each other (strongly connected components). A group must contain an activated server exactly when no link enters it from another group, and one server per such group suffices, so take the smallest-numbered server of each such group.