题目链接

题目描述

补充题：
现有n个编译项，编号为0 ~ n-1。给定一个二维数组，表示编译项之间有依赖关系。如[0, 1]表示1依赖于0。
若存在循环依赖则返回空；不存在依赖则返回可行的编译顺序。
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入： numCourses = 2, prerequisites = [[1,0]]
输出： [0,1]
解释： 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入： numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出： [0,2,1,3]
解释： 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入： numCourses = 1, prerequisites = []
输出： [0]

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 匹配 互不相同

拓展：

这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
通过 DFS 进行拓扑排序 - 一个关于 Coursera 的精彩视频教程（21 分钟），介绍拓扑排序的基本概念。
拓扑排序也可以通过 BFS 完成。
解题思路
方法一：拓扑排列（BFS法）
拓扑排序算法过程：

选择图中一个入度为0的点，记录下来
在图中删除该点和所有以它为起点的边
重复1和2，直到图为空或没有入度为0的点。

算法流程 ：
1、在开始排序前，扫描对应的存储空间（使用邻接表），将入度为 0 的结点放入队列。
2、只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减 1 以后，如果这个被减 1 的结点的入度为 0 ，就继续入队。
3、当队列为空的时候，检查结果集中的顶点个数是否和课程数相等即可。
（思考这里为什么要使用队列？如果不用队列，还可以怎么做，会比用队列的效果差还是更好？）
在代码具体实现的时候，除了保存入度为 0 的队列，我们还需要两个辅助的数据结构：
1、邻接表：通过结点的索引，我们能够得到这个结点的后继结点；
2、入度数组：通过结点的索引，我们能够得到指向这个结点的结点个数。
这个两个数据结构在遍历题目给出的邻边以后就可以很方便地得到。

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        if(numCourses == 0){
            return new int [0];
        }
        // 邻接表 数组
        HashSet<Integer>[] adj = new HashSet[numCourses];
        for(int i = 0; i < numCourses; ++i){
            adj[i] = new HashSet<Integer>();
        }
        // 入度
        int[] inDegree = new int[numCourses];
        for(int[] p : prerequisites){
            // 从p[1] 到 p[0]
            // 所以 p[1] 节点邻接表 加 p[0] 节点
            adj[p[1]].add(p[0]);
            // p[0] 节点入度加一
            ++inDegree[p[0]];
        }
        // 入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; ++i){
            if(inDegree[i] == 0){
                queue.offer(i);
            }
        }
        // 结果
        int[] res = new int[numCourses];
        // 当前结果集列表里的元素个数，正好可以作为下标
        int count = 0;
        while(!queue.isEmpty()){
            // 入度为 0 的节点
            Integer head = queue.poll();
            // 加入结果集 下标加一
            res[count++] = head;
            // 当前加入 节点 的邻接表  对应的 节点 入度都减一
            Set<Integer> successors = adj[head];
            for(Integer nextCourse : successors){
                --inDegree[nextCourse];
                if(inDegree[nextCourse] == 0){
                    queue.offer(nextCourse);
                }
            }
        }
        if(count == numCourses){
            return res;
        }
        return new int[0];
    }
}

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adj = new ArrayList<List<Integer>>();
        Queue<Integer> queue = new LinkedList<Integer>();
        int[] res = new int[numCourses];
        int pos = 0;
        Arrays.fill(res, -1); 
        for(int i = 0; i < numCourses; ++i){
            adj.add(new ArrayList<Integer>());
        }
        for(int[] cp : prerequisites){
            indegree[cp[0]]++;
            adj.get(cp[0]).add(cp[1]);
        }
        for(int i = 0; i < numCourses; ++i){
            if(indegree[i] == 0){
                queue.offer(i);

            }
        }
        while(!queue.isEmpty()){
            int k = queue.poll();
            res[pos++] = k;
            for(int i = 0; i < numCourses; ++i){
                if(adj.get(i).contains(k)){
                    indegree[i]--;
                    if(indegree[i] == 0){
                        queue.offer(i);
                    }
                }
            }
        }
        for(int val : indegree){
            if(val != 0){
                return new int[0];
            }
        }
        return res;
    }
}

时间复杂度 O(E+V) E为临边的个数， V为点的个数
空间复杂度 O(V)

如果是请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
则直接判断结果集元素个数是否等于课程个数不用记录结果

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses < 2){
            return true;
        }
        HashSet<Integer>[] adj = new HashSet[numCourses];
        for(int i = 0; i < numCourses; ++i){
            adj[i] = new HashSet<Integer>();
        }
        int[] indegree = new int[numCourses];
        for(int[] p : prerequisites){
            adj[p[1]].add(p[0]);
            ++indegree[p[0]];
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; ++i){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }
        int count = 0;
        while(!queue.isEmpty()){
            int head = queue.poll();
            count++;
            Set<Integer> set = adj[head];
            for(Integer s : set){
                --indegree[s];
                if(indegree[s] == 0){
                    queue.offer(s);
                }
            }
        }
        if(count == numCourses){
            return true;
        }
        return false;
    }
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adj = new ArrayList<List<Integer>>();
        Queue<Integer> queue = new LinkedList<>();
        // 保存入度的课程号
        for(int i = 0; i < numCourses; ++i){
            adj.add(new ArrayList<Integer>());
        }
        for(int[] cp : prerequisites){
            adj.get(cp[1]).add(cp[0]);
            indegree[cp[1]]++;
        }
        for(int i = 0; i < numCourses; ++i){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()){
            int k = queue.poll();
            for(int i = 0; i < numCourses; ++i){
                if(adj.get(i).contains(k)){
                    indegree[i]--;
                    if(indegree[i] == 0){
                        queue.offer(i);
                    }
                }                
            }
        }
        for(int i : indegree){
            if(i != 0){
                return false;
            }
        }
        return true;
    }
}

返回顺序：

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Queue<Integer> q = new LinkedList<Integer>();
        int[] indegree = new int[numCourses];
        List<Integer> res = new LinkedList<>();
        List<List<Integer>> adj = new ArrayList<List<Integer>>();
        for(int i = 0; i < numCourses; ++i){
            adj.add(new ArrayList<Integer>());
        }
        for(int[] prerequisite : prerequisites){
            ++indegree[prerequisite[1]];
            adj.get(prerequisite[1]).add(prerequisite[0]);
        }
        for(int i = 0; i < numCourses; ++i){
            if(indegree[i] == 0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int k = q.poll();
            res.add(0, k);
            for(int i = 0; i < numCourses; ++i){
                if(adj.get(i).contains(k)){
                    --indegree[i];
                    if(indegree[i] == 0){
                        q.offer(i);
                    }
                }
            }
        }
        if(res.size() != numCourses){
            return new int[]{};
        }
        int[] ans = new int[res.size()];
        for(int i = 0; i < res.size(); ++i){
            ans[i] = res.get(i);
        }
        return ans;

    }
}

时间复杂度 O(E+V) E为临边的个数， V为点的个数
空间复杂度 O(V)

算法(leetcode 牛客网)

210. 课程表 I II 补充题：检测循环依赖 **

题目链接

题目描述

解题思路

方法一：拓扑排列（BFS法）