力扣 207 课程表

题意：给一组课程，里边有修课的先后顺序，查看能否把所有的课修完

思路： 把课程想成有向图，先修的课是出度，后修的课是入度

1. 用map记录每一个节点连接的出度节点们
2. 用in记录每一个节点的入度
3. 把入度为0的放到队列中
4. 遍历队列，每次pop一个节点，计数加一，
5. 遍历它连接的节点，并把每一个节点的入度减一，把入度为0的加入队列
6. 查看cnt和课程数是否相等

思想：拓扑排序

复杂度：时间O（n)，空间O(n)

class Solution {
    public boolean canFinish(int numCourses, int[][] p) {
        int[] in = new int[numCourses];
        Map<Integer, List<Integer>> map = new HashMap();
        
        for(int i=0;i<p.length;i++) {
            in[p[i][0]]++;
            List<Integer> temp = map.getOrDefault(p[i][1], new ArrayList<Integer>());
            temp.add(p[i][0]);
            map.put(p[i][1], temp);
        }
        
        Queue<Integer> q = new LinkedList<Integer>();
        for(int i=0;i<numCourses;i++) {
            if(in[i] == 0)
                q.add(i);
        }
        int cnt = 0;
        while(!q.isEmpty()) {
            int cur = q.poll();
            cnt++;
            if(map.containsKey(cur)) {
                for(int i: map.get(cur)) {
                    in[i]--;
                    if(in[i] == 0) {
                        q.add(i);
                    }
                }
            }
        }
        
        return cnt == numCourses;
    }
}