> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/graph-search/graph-theory/topological_sort/course-schedule.md).

# Course Schedule

## Course Schedule II ([LC.210](https://leetcode.com/problems/course-schedule-ii/))

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

```java
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

```java
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
}
```