字节高频题补充 检测循环依赖

和 力扣207.课程表 相似

• 循环依赖检测。如，[['A', 'B'], ['B', 'C'], ['C', 'D'], ['B', 'D']] => false，[['A', 'B'], ['B', 'C'], ['C', 'A']] => true（2021.4 字节跳动-幸福里-后端）
• 手撕代码：小王写了一个makefile，其中有n个编译项编号为0~n-1，他们互相之间有依赖关系。请写一个程序解析依赖，给出一个可行的编译顺序。（2021.03 字节跳动-系统部-后端）

解决这类问题的利器就是——拓扑排序。

拓扑排序算法过程：

1. 选择图中一个入度为0的点，记录下来

2. 在图中删除该点和所有以它为起点的边

3. 重复1和2，直到图为空或没有入度为0的点。

若给定一个依赖关系是[[0,2],[1,2],[2,3],[2,4]]，如图所示。

选择入度为0的节点，比如选择点0，记录至res；删除点0及以它为起点的边。 

 然后选择点1，同样记录下来；删除点1及以它为起点的边。

 入度为0的点现在只有点2，把它记录下来；删除点2及以它为起点的边。

同理。选择点3，记录下来；删除点3及以它为起点的边。 

 选择点4，记录下来；删除点4及以它为起点的边。

如果是循环依赖，可以使用res.size() == n 来判断图中是否有环。其中，n为点的个数。

    public List haveCircularDependency(int n, int[][] prerequisites){
        int[] inArray=new int[n];
        List> list=new LinkedList<>();
        List res=new LinkedList<>();
        Queue queue=new LinkedList<>();
        for(int i=0;i());
        }
        for(int i=0;i temp=list.get(num);
                for(int k:temp){
                    if(--inArray[k]==0){
                        queue.add(k);
                    }
                }
            }
        }
        if(res.size()==n){
            return res;
        }
        else {
            return null;
        }
    }