# 207. Course Schedule

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MagwqQO4bUOAlg5Vn4K%2F-Mah1PC0gaxcitUkKGfG%2Fimage.png?alt=media\&token=14902006-bc9a-4529-89b6-f132d61d6987)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MagwqQO4bUOAlg5Vn4K%2F-Mah1VFwho8FbcgBrc6G%2Fimage.png?alt=media\&token=042b81af-f05d-44f8-a1a5-621d457bc627)



You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `bi` first if you want to take course `ai`.

\[a, b] => b first : b -> a

\[1] first, \[0] is node, so cal indegree in \[0]

use topology sort



cal indegree, if indegree == 0 put into queue (means prerequs..), Then BFS

indegree 0 means it's a start point



for loop , look up which course first (\[1]) need  start point (means start from this



```java
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // topology order
        int indegree[] = new int[numCourses];
        int res = numCourses;
        for (int pair[] : prerequisites) { // why indegree, find indegree == 0 start to finish, that's the solution
            indegree[pair[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i< indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i); // add indegree == 0 as start point
            }
        }
        
        // [4,3] => graph: 3-4. => indegree => 3: 0, 4: 1
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            res--;
            for (int pair[] : prerequisites) {
                if (pre == pair[1]) { // when pair[1](prerequisites) match the start point
                    indegree[pair[0]]--; // do -- 
                    if (indegree[pair[0]] == 0) { // pair[0]'s indegree == 0, means pair[0] can be a new start point
                        queue.offer(pair[0]); // add start point
                    }
                }
            }
        }
        return res == 0; // means we finish all courses
    }
}
```



### new version

time: O(V+E)

space: O(n), n is numCourses

```java
class Solution {
    public boolean canFinish(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]]++;
        }
        
        int res = numCourses;
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int pos = queue.poll();
            res--;
            for (int next : graph[pos]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }
        return res == 0;
    }
}


/*
prerequisites = [[1,0]]

0 -> 1
*/
```
