197. Prerequisite Reachability Queries

Why this mechanism works

Propagate complete ancestor sets forward through topological order. For an edge u->v, every ancestor of u is also an ancestor of v, and u itself is a direct ancestor. Set union prevents shared prerequisite routes from duplicating facts.

State and boundaries

ancestors[v] contains discovered strict prerequisites of v. When u is processed, its ancestor set is complete.

Protocol

1. Obtain topological order and validate acyclicity.
2. Allocate an empty set per vertex.
3. For each ordered u and outgoing v, union ancestors[u] into ancestors[v] and add u.
4. Answer each query by set membership.

Visualization

0 -> 1 -> 3
 \-> 2 -> 3
ancestors[3] = {0,1,2}, with 0 included once

Python implementation

from kata_193 import topological_order

def prerequisite_queries(adj, queries):
    order = topological_order(adj)
    if len(order) != len(adj):
        raise ValueError('graph must be acyclic')
    ancestors = [set() for _ in adj]
    for u in order:
        for v in adj[u]:
            ancestors[v].update(ancestors[u])
            ancestors[v].add(u)
    return [u in ancestors[v] for u, v in queries]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 prerequisite_queries: order = topological_order(adj)
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]

L7 prerequisite_queries: ancestors = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; _=[1, 2]

L7 prerequisite_queries: ancestors = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; _=[3]

L7 prerequisite_queries: ancestors = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; _=[]

L7 prerequisite_queries: ancestors = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), set(), set(), set()]

L8 prerequisite_queries: for u in order:
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), set(), set(), set()]; u=0

L9 prerequisite_queries: for v in adj[u]:
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), set(), set(), set()]; u=0; v=1

L11 prerequisite_queries: ancestors[v].add(u)
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), {0}, set(), set()]; u=0; v=1

... 8 intermediate state changes omitted ...

L8 prerequisite_queries: for u in order:
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), {0}, {0}, {0, 1, 2}]; u=3; v=3

L12 prerequisite_queries: return [u in ancestors[v] for u, v in queries]
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), {0}, {0}, {0, 1, 2}]; u=0; v=3

L12 prerequisite_queries: return [u in ancestors[v] for u, v in queries]
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), {0}, {0}, {0, 1, 2}]; u=1; v=2

L12 prerequisite_queries: return [u in ancestors[v] for u, v in queries]
adj=[[1, 2], [3], [3], []]; queries=[(0, 3), (1, 2), (3, 3)]; order=[0, 1, 2, 3]; ancestors=[set(), {0}, {0}, {0, 1, 2}]; u=3; v=3

L4 prerequisite_queries: order = topological_order(adj)
adj=[[], []]; queries=[(0, 1)]; order=[0, 1]

L7 prerequisite_queries: ancestors = [set() for _ in adj]
adj=[[], []]; queries=[(0, 1)]; order=[0, 1]; _=[]

L7 prerequisite_queries: ancestors = [set() for _ in adj]
adj=[[], []]; queries=[(0, 1)]; order=[0, 1]; ancestors=[set(), set()]

L8 prerequisite_queries: for u in order:
adj=[[], []]; queries=[(0, 1)]; order=[0, 1]; ancestors=[set(), set()]; u=0

L8 prerequisite_queries: for u in order:
adj=[[], []]; queries=[(0, 1)]; order=[0, 1]; ancestors=[set(), set()]; u=1

L12 prerequisite_queries: return [u in ancestors[v] for u, v in queries]
adj=[[], []]; queries=[(0, 1)]; order=[0, 1]; ancestors=[set(), set()]; u=0; v=1

L12 prerequisite_queries: return [u in ancestors[v] for u, v in queries]
adj=[[], []]; queries=[(0, 1)]; order=[0, 1]; ancestors=[set(), set()]; u=1

Why the solution is correct

Every propagated fact corresponds to an existing path extended by one edge. Conversely, every path to v ends at some predecessor u, whose complete ancestors are propagated before v is processed. Thus all and only strict reachability facts are present when queries are answered.

Time and space

O(V+E+E*V+Q) worst-case time with hash sets and Q queries; O(V^2+E+Q) total storage including output. Dense reachability can be quadratic even in a sparse DAG.

Common mistakes

Adding a node to its own ancestor set changes self-query semantics. Summing counts cannot answer which prerequisite is shared by two routes.

Reasoning card

Transfer exercise

Represent ancestor sets as bit masks and discuss word-level speedups and Python big-integer costs.