All problems

Power Outage Cascade

Medium · topological sort

A town's power network has n stations, numbered 0 to n - 1. Each entry [a, b] in links means station a sends power to station b. No station sends power to itself, and the same link may be listed more than once.

A station with no incoming link makes its own power, so it only goes dark if it is one of the broken stations. Any other station keeps its power as long as at least one station sending it power is lit. It goes dark the moment all the stations sending it power are dark.

The stations in broken fail first and stay dark. Then the blackout spreads by the rule above until nothing more changes. Return how many stations are dark at the end, counting the broken ones.

Examples

Example 1

Input: n = 5, links = [[0, 2], [1, 2], [2, 3], [2, 4], [3, 4]], broken = [0]

Output: 1

Station 2 is also supplied by station 1, which is still lit, so the blackout stops at station 0.

Example 2

Input: n = 5, links = [[0, 2], [1, 2], [2, 3], [2, 4], [3, 4]], broken = [0, 1]

Output: 5

Station 2 loses both suppliers, then station 3 loses its only supplier, and finally station 4 loses both of its suppliers.

Example 3

Input: n = 4, links = [[0, 1], [1, 2], [2, 3]], broken = [1]

Output: 3

Station 0 still has power, but stations 1, 2 and 3 are dark. Power only flows forwards.

Constraints