# 210. Course Schedule II

![](/files/-MamEbS1Hyn4pABarAhw)

![](/files/-MamEfFHgyz3mzPx5H8M)

time: O(V+E), refer to <https://www.educative.io/edpresso/what-is-topological-sort>

space: O(n)

same as 207's solution, use topology sort , just when   &#x20;

```java
if (indegree[p[0]] == 0) {
```

record the result

and at last check res'length == numCouses

```java
return (k == numCourses) ? res : new int[0];

```

![](/files/-MbQh70bYT4Acv53WAyc)

這個例子 , 照理說 indegree 都會是 1 => indegree: \[1, 1], so res\[] 不應該有計算過, 但是要注意到...

int res\[] = new int\[numCourses]; ⇒ \[0, 0]

因為初始化, int 是基本型台,  所以整個陣列就會是 0, 所以如果 res size 是 2, 就會變成 \[0, 0]

所以最後才要加上這行, 不然無法呈現 \[] 的結果

return (k == numCourses) ? res : new int\[0];

```java
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int indegree[] = new int[numCourses];
        int res[] = new int[numCourses];
        
        for (int p[] : prerequisites) {
            indegree[p[0]]++;
        }
        
        int k = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
                res[k++] = i;
            }
        }
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            for (int p[] : prerequisites) {
                if (pre == p[1]) {
                    indegree[p[0]]--;
                    if (indegree[p[0]] == 0) {
                        queue.offer(p[0]);
                        res[k++] = p[0];
                    }
                }
            }
        }
        return (k == numCourses) ? res : new int[0];
    }
}
```

## better one

```java
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List graph[] = new ArrayList[numCourses];
        int indegree[] = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }
        
        for (int edge[] : prerequisites) {
            graph[edge[1]].add(edge[0]); //construct graph
            indegree[edge[0]]++;
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int numChoose = 0;
        int order[] = new int[numCourses];
        while (!queue.isEmpty()) {
            int nowPos = queue.poll();
            order[numChoose++] = nowPos;
            for (int i = 0; i < graph[nowPos].size(); i++) {
                int nextPos = (int)graph[nowPos].get(i);
                indegree[nextPos]--;
                if (indegree[nextPos] == 0) {
                    queue.offer(nextPos);
                }
            }
        }
        return numChoose == numCourses ? order : new int[]{};
    }
}

// [0, 1] => 1 -> 0
```

### new version

time: O(V+E), refer to <https://www.educative.io/edpresso/what-is-topological-sort>

space: O(n)

```java
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> graph[] = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int p[] : prerequisites) {
            graph[p[1]].add(p[0]); // start -> end
            indegree[p[0]]++;
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] order = new int[numCourses];
        int orderIdx = 0;
        while (!queue.isEmpty()) {
            int pos = queue.poll();
            order[orderIdx++] = pos;
            
            for (int next : graph[pos]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return orderIdx == numCourses ? order : new int[]{};
    }
}


/*
prerequisites = [[1,0]]

0 -> 1
*/

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/topology/210.-course-schedule-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.