Why it works
- A dead end is safe. A node is safe exactly when all its arrows lead to safe nodes, so it joins the queue once its count of exits not known safe reaches 0.
- A node on a loop always keeps the arrow that goes on round the loop, and so does a node with an arrow into a loop: their count never reaches 0.
- The card counts arrows in and starts from what waits for nothing; here the arrows are walked backwards, so the count is of arrows out and the start is the dead ends.
Complexity
Time O(n + e + n log n) for n nodes and e arrows: each arrow is reversed and walked back once, each node enters the queue at most once, and the safe nodes are sorted at the end. Memory O(n + e) for the reversed arrows, the counts and the queue.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗