Course Schedule

medium

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

Return true if you can finish all courses. Otherwise, return false.

Test Cases

Copy an input into the main harness and Run to verify

Input

numCourses = 2, prerequisites = [[1,0]]

Expected Output

true

Input

numCourses = 2, prerequisites = [[1,0],[0,1]]

Expected Output

false

Explanation: Course 0 and 1 depend on each other — a cycle.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

Hints

Hint 1 — click to reveal

This is cycle detection in a directed graph.

Hint 2 — click to reveal

Kahn's algorithm: repeatedly remove nodes with zero remaining prerequisites.

Java Compiler