This is a topological sort problem. Track each node's in-degree and process zero-in-degree nodes first.

Course Schedule II

medium

Acceptance: 46%

GraphsTopological SortBFS

Given n courses (labeled 0 to n-1) and prerequisite pairs indicating which course must come before another, produce a valid order in which to take all courses. If multiple valid orderings exist, return any one. If no valid ordering exists (due to circular dependencies), return an empty list.

Examples

Example 1:

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

Output:[0,1,2]

Explanation: Courses 0 and 1 have no prerequisites and can be taken first; then course 2.

Example 2:

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

Output:[]

Explanation: A cycle makes it impossible to schedule all courses.

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 II

Examples

Hints

Related Problems