207. 课程表 - Java 拓扑排序 Kahn算法

原题地址：https://leetcode.cn/problems/course-schedule/

题解

对于一系列给定的点和边，如果有有向边A->B，则称A是B的依赖，完成事件时需要先完成A才能继续进行B，求能够完成所有事件的事件顺序叫做拓扑排序

不管是DFS还是Kahn算法，拓扑排序的原理都是相通的：将集合V中入度为0的点全部转移至一个集合S，每次加入集合S时将该点所有的出度边全部删除，然后检查删除边后是否有新的入度为0的点，如果有继续重复上述步骤直至无法继续更新

对于是否能够完成所有事件，排序后检查所有点入度是否均为0即可；对于拓扑排序得到的序列，在每次将点加入集合S时再将其加入一个List维护即可

Kahn算法：

Kahn算法是一种基于BFS的拓扑排序，其中BFS的队列即为这里的集合S，用一个出度表out记录下每个点指向的点，再用一个入读表in记录每个点的入度

我们先将所有入度为0的点全部加入集合S，每次取出点时遍历其out表，将指向的所有点入度-1即为删除这两点间的有向边，每次更新完入度后检查该被指向点入度是否为0，如果为0则加入队列中

BFS完毕后检查入度是否全为0即可，若有非0点则返回false

时间复杂度：O(E+V)

空间复杂度：O(E+V)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> out=new ArrayList<>();
        int[] in=new int[100001];
        Queue<Integer> Kahn=new LinkedList<>();

       for (int i=0;i<numCourses;i++){
           out.add(new LinkedList<>());
       }

        for(int i=0;i<prerequisites.length;i++){
            //补充出度表
            out.get(prerequisites[i][1]).add(prerequisites[i][0]);
            //入度数++
            in[prerequisites[i][0]]++;
        }

        for (int i=0;i<numCourses;i++){
            if(in[i]==0){
                Kahn.add(i);
            }
        }

        int course;
        while (!Kahn.isEmpty()){
            course=Kahn.remove();
            for (int i=0;i<out.get(course).size();i++){
                in[out.get(course).get(i)]--;
                if(in[out.get(course).get(i)]==0){
                    Kahn.add(out.get(course).get(i));
                }
            }
        }

        for (int i:in){
            if(i!=0)return false;
        }
        return true;
    }
}