---
# System prepended metadata

title: 0207. Course Schedule
tags: [Leetcode, BFS, FaceBook, Topological Sort, Medium]

---

# 0207. Course Schedule
###### tags: `Leetcode` `FaceBook` `Medium` `BFS` `Topological Sort`
Link: https://leetcode.com/problems/course-schedule/
## 思路
和[0210. Course Schedule II](https://hackmd.io/EzKnR3KLQayEp_SAYuXaYQ)一样的做法～
先建图再bfs
有向图所以要分开存parent的所有child以及child的parent个数
无向图存每个node的所有边即可，这样就通过一个```List<List<Integer>>```知道所有信息～(例如: [0310. Minimum Height Trees](https://hackmd.io/2yyf1znOQlCdQ-3mRGkkSw))
## Code
```java=
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0;i < numCourses;i++){
            graph.add(new ArrayList<>());
        }
        int[] count = new int[numCourses];
        for(int[] prerequisite:prerequisites){
            int u = prerequisite[0];
            int v = prerequisite[1];
            graph.get(v).add(u);
            count[u]++;
        }
        
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0;i < count.length;i++){
            if(count[i]==0) q.add(i);
        }
        while(!q.isEmpty()){
            int curr = q.poll();
            for(int next:graph.get(curr)){
                count[next]--;
                if(count[next]==0) q.add(next);
            }
        }
        for(int i = 0;i < count.length;i++){
            if(count[i]>0) return false;
        }
        return true;
    }
}
```