A data pipeline has n processing stages. Some stages must run before others, given as directed constraints: an edge u v means stage u must run strictly before stage v. The whole pipeline can be scheduled only if there is an ordering of all n stages that respects every constraint. Determine whether such an ordering exists.
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).
Print YES if a valid ordering of all stages exists, otherwise print NO.
u u, which makes ordering impossible)Example 1
Input
3 2 0 1 1 2
Expected
YES
Explanation
The constraints form the chain 0 -> 1 -> 2 with no cycle, so the ordering 0, 1, 2 works: YES.
Example 2
Input
2 2 0 1 1 0
Expected
NO
Explanation
0 must precede 1 and 1 must precede 0, a contradiction (a 2-cycle), so no ordering exists: NO.
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 →