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. In short,

Given n nodes and a list of directed edges, find one topological ordering.

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.

Approach

Step 1 Build a graph

Step 2 topo sort with BFS
    - count indegree
    - put 0 indegree (no incoming edges) to queue
    - delete that node from the queue and all its outgoing edges (decrease the indegree of its neighbor)

Clear Version

public int[] findOrder(int numCourses, int[][] prereqs) {
    // Step 1 Build a graph
    Map<Integer, List<Integer>> graph = buildGraph(numCourses, prereqs);
    // Step 2 Topo Sort (BFS)
    // count indegrees
    int[] indegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        for (int neighbor : graph.get(i)) {
            indegree[neighbor]++;
        }   
    }
    // init queue
    Queue<Integer> queue = new LinkedList<>();
    List<Integer> courseOrder = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue.offer(i);
            courseOrder.add(i);
        }
    }
    // bfs
    int current;
    while (!queue.isEmpty()) {
        current = queue.poll();
        for (int neighbor : graph.get(current)) {
            indegree[neighbor]--;
            if (indegree[neighbor] == 0) {
                queue.offer(neighbor);
                courseOrder.add(neighbor);
            }
        }
    }
    // if there's cycle
    if (courseOrder.size() == numCourses) {
        return courseOrder.stream().mapToInt(Integer::intValue).toArray();
    } else {
        return new int[] {};
    }
}

// edges are directed only add once
private Map<Integer, List<Integer>> buildGraph(int n, int[][] edges) {
    // adjacency list representation
    Map<Integer, List<Integer>> adjList = new HashMap<>();
    // create all vertices
    for (int i = 0; i < n; i++) {
        adjList.put(i, new LinkedList<Integer>());
    }
    // add all directed edges [a <-- b]
    for (int[] edge : edges) {
        int a = edge[0];
        int b = edge[1];
        adjList.get(b).add(a);
    }
    return adjList;
}

Short Version

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
}