# 1136. Parallel Courses
###### tags: `Leetcode` `BFS` `FaceBook`
Link: https://leetcode.com/problems/parallel-courses/
## 思路
和[210.Course Schedule II](https://hackmd.io/EzKnR3KLQayEp_SAYuXaYQ)的思路一样
用```List<List<Integer>>``` 存下来每节课的next，并且记录每节课的prev一共有多少
然后用BFS 首先把prev num = 0的课加进去，然后看上了这节课之后，哪些course的prev变成0，以此循环
这道题不同的地方就是因为要算最少几个学期都上完，因此用层序遍历
同时判断能不能把所有课上完可以不用最后再遍历一次每个course的prev，而换成在bfs的过程中，记录上了多少课，跟课程总数比较
## Code

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        List<List<Integer>> prev = new ArrayList<>();
        for(int i = 0;i < n;i++){
            prev.add(new ArrayList<>());
        }
        
        int[] prevNum = new int[n];
        for(int i = 0;i < relations.length;i++){
            int prevCourse = relations[i][0];
            int nextCourse = relations[i][1];
            prev.get(prevCourse-1).add(nextCourse-1);
            prevNum[nextCourse-1]++;
        }
        
        int ans = 0;
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0;i < n;i++){
            if(prevNum[i]==0){
                q.add(i);
            }
        }
        
        while(!q.isEmpty()){
            int size = q.size();
            ans++;
            for(int i = 0;i < size;i++){
                int curr = q.poll();
                List<Integer> nextList = prev.get(curr);
                for(int next:nextList){
                    prevNum[next]--;
                    if(prevNum[next]==0){
                        q.add(next);
                    }
                }
            }
        }
        
        for(int i = 0;i < n;i++){
            if(prevNum[i]>0){
                return -1;
            }
        }
        return ans;
    }
}