← 返回 amazon 的题目列表Course Schedule: Can Finish All Courses
类型:online_judge
Problem: Course Schedule Cycle Detection
You are given n courses labeled from 0 to n - 1, and an array of prerequisite pairs prerequisites.
prerequisites[i] = [a, b] means that to take course a, you must first take course b.
Determine whether it is possible to finish all courses.
Return true if all courses can be completed; otherwise return false.
Input Format
The first line contains two integers n and m:
n is the number of courses
m is the number of prerequisite relations
The next m lines each contain two integers a b, meaning course b must be completed before course a.
Output Format
Print true if all courses can be completed
Otherwise print false
Constraints
1 <= n <= 10^5
0 <= m <= 2 * 10^5
0 <= a, b < n
a != b
Example
Input:
2 1
1 0
Output:
true
Explanation: You can take course 0 first, then course 1.
Example
Input
2 1
1 0
Output
true