Before writing Kahn's algorithm it helps to be crisp about what a topological order is. There are n tasks 0 .. n-1, and each pair (u, v) in edges means task u must come before task v.
Implement is_topological_order(n, edges, order) -> bool. Return True exactly when:
ordercontains every task0 .. n-1exactly once (no missing, extra or repeated tasks), and- for every edge
(u, v),uappears earlier inorderthanv.
edges = [(0, 2), (1, 2), (2, 3)]
is_topological_order(4, edges, [1, 0, 2, 3]) # True (0 and 1 can go in either order)
is_topological_order(4, edges, [0, 2, 1, 3]) # False (2 comes before its prerequisite 1)
is_topological_order(4, edges, [0, 1, 2]) # False (task 3 is missing)
Constraints: 0 <= n <= 10^5, up to 2 * 10^5 edges, edges may repeat, and a self-loop (v, v) can never be satisfied. It should run in O(n + E): don't call order.index(...) for every edge.
Show hint
record pos[task] = index once, then every edge just needs pos[u] < pos[v].