Count Unique Dependents in a Referral DAG

Given named nodes and a dependency DAG, compute how many unique nodes directly or indirectly depend on each node. An edge [a,b] means a depends on b, so a contributes to b's count, not the other way around.

Implement referral_counts(nodes: string[], edges: string[][]) -> int[]. Return one count per node in the same order as nodes; this parallel-array output is a portable representation of the source's name-to-count map.

Constraints & Assumptions

• Between 0 and 2000 unique nonempty node names and at most 10000 edges. Each edge contains exactly two names.
• Discard an edge if either endpoint is absent from nodes. Excluded nodes must not create paths connecting known nodes.
• The remaining graph is a DAG. Duplicate edges may occur and must not multiply reachability counts.
• Count distinct reachable dependents, excluding the node itself. Shared descendants reached by multiple paths count once.
• Isolated nodes have count zero. Names are case-sensitive.

Example

nodes = ["A","B","C","D","E"]
edges = [["B","A"],["C","A"],["D","B"],["D","C"],
         ["E","ghost"],["ghost","A"]]
result = [3,1,1,0,0]

D contributes only once to A. Ignoring the unknown node does not create an E-to-A relationship.

Explain a topological-order approach and why adding child counts is insufficient when dependency paths merge. Compare set or bitset propagation with performing a graph search separately for each node, including time and memory tradeoffs.

Hint: Counts alone lose overlap information

When two direct dependents share another dependent, you need enough information to union their reachable nodes without counting that shared node twice.

Count Distinct Dependents in a Dependency DAG

Approach

Map known names to their input-order indices and discard edges with either unknown endpoint before building paths. Keep each valid edge once, directed from dependent a to dependency b. Initialize each node bitset with itself. Process this directed DAG in topological order: nodes with no incoming dependents start ready, and a node becomes ready only after every direct dependent has propagated to it. For each a-to-b edge, union the completed bitset of a into b. By topological induction, a bitset contains exactly the node itself and every node depending on it through one or more paths. Union is idempotent, so shared descendants and duplicate paths never inflate counts. Subtract one from each final population count and return counts in the original node order. Adding child counts alone loses overlap information and overcounts diamonds. With V nodes, E input edges, and machine-word width w, packed propagation takes O(V+E+(V+E)ceil(V/w)) expected time including name lookup and deduplication, and O(V+E+V ceil(V/w)) words of space; string hashing also costs the characters inspected. Explicit sets offer the same union semantics with up to O(EV+V^2) element work and O(V^2) stored entries, but may help for sparse reachability. An independent graph search from each node on reversed adjacency avoids storing all reachability sets and uses O(V+E) working space, while taking O(V(V+E)) time. Python uses packed integer bitsets, Java uses BitSet, and the other references use fixed-width packed words.

• Time complexity: O(V+E+(V+E) ceil(V/w)) expected word operations, plus name hashing.
• Space complexity: O(V+E+V ceil(V/w)) words, plus node-name storage.