A college has n modules numbered 0 .. n-1. Its rulebook lists rules[i] = [a, b]: module a must be passed before module b. The rules never form a cycle. Module a is required before module b when a chain of one or more rules leads from a to b.
The registrar wants the shortest rulebook that keeps exactly the same "required before" relation. For an acyclic rulebook that shortest set is unique once repeated copies of the same rule are merged, so describe it by the rules to drop:
- a rule is dropped if the same pair
[a, b]already appeared at a smaller index (the first copy is the one considered for keeping); - otherwise it is dropped if
bcan be reached fromawithout using any copy of the rule[a, b].
Return the indices of the dropped rules in increasing order.
Examples
Input: n = 4, rules = [[0, 1], [1, 2], [0, 2], [2, 3], [0, 3], [1, 2]]
Output: [2, 4, 5]
Explanation: rule 2 (0 before 2) follows from 0 -> 1 -> 2, rule 4 (0 before 3)
follows from 0 -> 1 -> 2 -> 3, and rule 5 repeats rule 1.
Input: n = 3, rules = []
Output: []
Input: n = 3, rules = [[2, 0], [2, 0]]
Output: [1]
Constraints
1 <= n <= 3000,0 <= len(rules) <= 3 * 10**4a != b, and the rules contain no cycle- Target: about O(m * n / 64) time for
mrules. Searching the graph again for every rule is too slow.
Goals
- Decide when a direct rule already follows from a chain of other rules
- Compute every module's set of later modules in one pass in reverse topological order
- Use Python integers as bitsets so each set operation is fast