200. Dependency Impact Counts

Why this mechanism works

A node's downstream set consists of each direct successor plus that successor's downstream set. Process reverse topological order so every successor summary is complete before combining it. Counts alone are insufficient because two successors may share the same dependent.

State and boundaries

downstream[u] is the set of distinct descendants of u. Reverse order ensures every set read from a successor is final.

Protocol

1. Validate a topological order.
2. Allocate one empty set per vertex.
3. Process vertices in reverse order.
4. Add each successor and union its downstream set.
5. Return the set sizes in vertex order.

Visualization

0 -> 1 -> 3
 \-> 2 -> 3
downstream[0] = {1,2,3}
count is 3, not (1+1)+(1+1)=4

Python implementation

from kata_193 import topological_order

def dependency_counts(adj):
    order = topological_order(adj)
    if len(order) != len(adj):
        raise ValueError('graph must be acyclic')
    downstream = [set() for _ in adj]
    for u in reversed(order):
        for v in adj[u]:
            downstream[u].add(v)
            downstream[u].update(downstream[v])
    return [len(nodes) for nodes in downstream]

Worked execution

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

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

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; _=[1, 2]

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; _=[3]

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; _=[]

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; downstream=[set(), set(), set(), set()]

L8 dependency_counts: for u in reversed(order):
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; downstream=[set(), set(), set(), set()]; u=3

L8 dependency_counts: for u in reversed(order):
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; downstream=[set(), set(), set(), set()]; u=2

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

... 9 intermediate state changes omitted ...

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; downstream=[{1, 2, 3}, {3}, {3}, set()]; u=0; v=2; nodes={1, 2, 3}

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; downstream=[{1, 2, 3}, {3}, {3}, set()]; u=0; v=2; nodes={3}

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; downstream=[{1, 2, 3}, {3}, {3}, set()]; u=0; v=2; nodes=set()

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1, 2], [3], [3], []]; order=[0, 1, 2, 3]; downstream=[{1, 2, 3}, {3}, {3}, set()]; u=0; v=2

L4 dependency_counts: order = topological_order(adj)
adj=[[1], [2], []]; order=[0, 1, 2]

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1], [2], []]; order=[0, 1, 2]; _=[1]

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1], [2], []]; order=[0, 1, 2]; _=[2]

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1], [2], []]; order=[0, 1, 2]; _=[]

L7 dependency_counts: downstream = [set() for _ in adj]
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[set(), set(), set()]

L8 dependency_counts: for u in reversed(order):
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[set(), set(), set()]; u=2

L8 dependency_counts: for u in reversed(order):
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[set(), set(), set()]; u=1

L9 dependency_counts: for v in adj[u]:
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[set(), set(), set()]; u=1; v=2

... 5 intermediate state changes omitted ...

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[{1, 2}, {2}, set()]; u=0; v=1; nodes={1, 2}

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[{1, 2}, {2}, set()]; u=0; v=1; nodes={2}

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[{1, 2}, {2}, set()]; u=0; v=1; nodes=set()

L12 dependency_counts: return [len(nodes) for nodes in downstream]
adj=[[1], [2], []]; order=[0, 1, 2]; downstream=[{1, 2}, {2}, set()]; u=0; v=1

Why the solution is correct

Every inserted vertex is reachable through a direct successor. Every nonempty path begins with such a successor, whose completed set includes the rest of the path's endpoint. Set union removes duplicate routes to the same endpoint, giving exactly the distinct downstream vertices.

Time and space

O(V+E+E*V) worst-case time and O(V^2+E) auxiliary storage; O(V) returned counts.

Common mistakes

Adding successor counts overcounts shared descendants in a diamond. Processing forward topological order reads incomplete successor summaries.

Reasoning card

Transfer exercise

Return the downstream set itself for change-impact analysis, then discuss the cost of maintaining it after edge insertions.