Why not List [] for the adjacency list?

Java cannot create generic arrays: new List [n] is a compile error, and new List[n] compiles only with an unchecked warning. A List > filled in a loop avoids both. If you want primitives all the way, build an int[][] in two passes: count each course's outgoing pairs, allocate, then fill.

MediumGraphs

Course Schedule

Q: Why does a boolean visited array give wrong answers?

A single boolean[] cannot tell "on the current path" from "finished". In {{1, 0}, {2, 0}, {3, 1}, {3, 2}} course 3 is reached from 1 and again from 2, which is not a loop. Either use three states as here, or two arrays: visited and onPath, clearing onPath[course] on the way out.

Q: Can the recursion throw StackOverflowError?

Each hasLoop frame is small, and the default thread stack holds many thousands of them, so the 500-course chain here is fine. Graphs with hundreds of thousands of courses in one chain can overflow; Kahn's version, which only uses a queue, cannot.

Q: ArrayDeque or LinkedList for the queue?

ArrayDeque is backed by a growing array, so add and poll touch no extra node objects; LinkedList allocates a node for every element. Both implement Queue, and both box the int course into an Integer.

Q: How do I return a valid order instead of a boolean?

In the Kahn version, make an int[] order = new int[numCourses] and write order[taken++] = course where the loop counts. Return order when taken == numCourses, otherwise new int[0].

There are num_courses courses, numbered 0 to num_courses - 1. You get an array prerequisites of pairs [a, b], each meaning that course b has to be finished before course a can start. Return true if there is an order in which you can finish every course, and false if there is not.

Think of each pair as an arrow from b to a. The courses can all be finished exactly when those arrows never form a loop: a loop means each course on it waits for another one on it, so none of them can ever start. A pair [a, a], a course that needs itself, is the smallest loop. The same pair may appear more than once, which changes nothing. With no pairs at all, every course can be taken in any order, so the answer is true.

Examples

Input

num_courses = 5
prerequisites = [[2, 0], [2, 1], [3, 2], [4, 3]]

OutputtrueWhyTake 0 and 1 first, which unlocks 2, then 3, then 4. No arrow ever leads back.

Input

num_courses = 4
prerequisites = [[1, 0], [2, 1], [3, 2], [1, 3]]

OutputfalseWhyCourse 1 needs 3, 3 needs 2 and 2 needs 1: the loop 1 → 2 → 3 → 1 never lets any of them start. Course 0 alone is not enough.

Constraints

Courses: 1 ≤ num_courses ≤ 500
Pairs: 0 ≤ prerequisites.length ≤ 1,000
Values: 0 ≤ a, b < num_courses
Repeats: A pair can repeat, and a can equal b (a course that needs itself).
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

2 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.