Construct a directed graph from the prerequisites and check for the presence of cycles.

Course Schedule

medium

Acceptance: 47%

GraphsTopological SortBFS

There are n courses labeled 0 through n-1 with prerequisite constraints: some courses must be completed before others. Given these dependency pairs, determine whether it is possible to complete all courses (i.e., the dependency graph contains no cycles).

Examples

Example 1:

Input:numCourses = 3, prerequisites = [[1,0],[2,1]]

Output:true

Explanation: Take course 0, then 1, then 2. The dependency chain has no cycle.

Example 2:

Input:numCourses = 3, prerequisites = [[0,1],[1,2],[2,0]]

Output:false

Explanation: Courses 0, 1, and 2 form a circular dependency.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Course Schedule

Examples

Hints

Related Problems