A library has n modules forming a directed acyclic graph. A directed edge u v means module u is required before module v (so v is downstream of u). For each module, count how many distinct modules are reachable from it by following directed edges — that is, its number of descendants (not counting itself). Output one count per module.
Line 1: two integers n and m — the number of nodes (labeled 0 through n-1) and the number of directed edges.
Each of the next m lines: two integers u v, a directed edge from u to v (read as: u must come before v).
It is guaranteed the graph is acyclic, with no self-loops and no duplicate edges.
One line with n space-separated integers: the descendant count of node 0, node 1, ..., node n-1.
Example 1
Input
4 3 0 1 1 2 0 2
Expected
2 1 0 0
Explanation
From 0 you reach 1 and 2 (count 2). From 1 you reach 2 (count 1). Node 2 and node 3 reach nothing (0 each).
Example 2
Input
3 0
Expected
0 0 0
Explanation
No edges, so no module has any descendant: all counts are 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →