A build system has n jobs. A directed edge u v means job v depends on job u, so v cannot begin until u has finished. A job with no incoming dependency edges can be started right away. A self-loop u u counts as an incoming edge, so a job with a self-loop cannot start immediately. Count how many jobs can be started immediately.
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).
A single integer: the number of jobs with no incoming edges.
Example 1
Input
4 3 0 2 1 2 2 3
Expected
2
Explanation
Jobs 0 and 1 have no incoming edges; jobs 2 and 3 do. So 2 jobs can start immediately.
Example 2
Input
3 3 0 1 1 2 2 0
Expected
0
Explanation
Every job has an incoming edge (a 3-cycle), so none can start immediately: 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 →