A build has n targets, numbered 0 to n - 1. Each pair [u, v] in edges says target v can't start until target u has finished. The edges contain no cycles; the same pair may be listed twice.
The build runs in whole time steps with unlimited parallel workers. Every target takes exactly one step, and it is built in the earliest step at which all of its prerequisites are done: targets with no prerequisites are built in step 0, and any other target is built one step after its latest-finishing prerequisite.
A target is a bottleneck if it is the only target being built during its step: nothing else can overlap with it, so it holds up the whole build.
Write
def find_bottlenecks(n: int, edges: list[list[int]]) -> list[int]
returning all bottleneck targets in increasing order.
# 0 ──► 1 ──► 3 ──► 4
# 0 ──► 2 ──► 3
find_bottlenecks(5, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]]) # [0, 3, 4]
# step 0: {0} step 1: {1, 2} step 2: {3} step 3: {4}
find_bottlenecks(4, [[0, 1], [2, 3]]) # [] steps: {0, 2}, {1, 3}
find_bottlenecks(3, [[0, 2], [1, 2], [0, 1]]) # [0, 1, 2] 2 waits for 1, which waits for 0
find_bottlenecks(1, []) # [0]
Constraints: 0 <= n <= 200,000, up to 200,000 edges. Simulating the build by rescanning every target at every step is quadratic; compute each target's step in one pass.
Show hint
Process targets in topological order (Kahn's algorithm, peeling off targets whose in-degree reaches 0). A target's step is 1 + max(step of its prerequisites). Then count how many targets share each step.