Course Schedule

Course Schedule II (LC.210)

There are n courses a student has to take, labeled from 0 to n-1. Some courses have prerequisites. For example, [0,1] you have take course 1 before taking course 0.

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

Return any correct ordering is fine. If it is impossible to finish all courses, return an empty array.

Example

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3] or [0, 2, 1, 3]

Assume no duplicate edges.

Analysis

BFS is easier to implement than a DFS on this edge list structure. Create a Map to store the indegree for each node. Also, we want to convert the edge lists to adjacency lists so we know their neighbors. Then just do topological sort.

Code

public List<Integer> findOrder(int numCourses, int[][] prerequisites) {
    // Step 1 Count indegree an build an adjacency list
    int[] indegree = new int[numCourses];
    // adjacency list
    List<List<Integer>> graph = new ArrayList<>(numCourses);
    for (int i = 0; i < numCourses; i++)
        graph.add(new ArrayList<>());
    for (int i = 0; i < prerequisites.length; i++) {
        indegree[prerequisites[i][0]]++;
        graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
    }

    // Step 2 topo sort
    List<Integer> queue = new ArrayList<>();
    for (int i = 0; i < numCourses; i++)
        if (indegree[i] == 0)
            queue.add(i);
    for (int i = 0; i < queue.size(); i++) {
        Integer current = queue.get(i);
        for (Integer neighbor : graph.get(current)) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0)
                queue.add(neighbor);
        }
    }

    return (queue.size() == numCourses) ? queue : new ArrayList<>();
    // queue.stream().mapToInt(Integer::intValue).toArray() for int array
}