问题背景

给你一组课，课和课之间互不相同，课与课之间可以有依赖。如果要学习某一课必须先学习其依赖的课。

比如上例，课程A没有任何依赖，可以直接学习。
课程B依赖课程A，D。

思路

这里统一用一种方案解决：
首先将原数据给出的依赖关系转换为有向图结构
List[] 其长度为课程数，每个节点为一个List其中保存的是每个节点的next节点。

此外需要维护每个节点的入度 。即多少个节点指向此节点，如果这个为0，说明这个节点没有依赖。在题意的语义环境下则意味着，这门课没有依赖，可以直接学习。

后面进行广度优先搜索，将所有入度 已经为0的节点入队并加入结果集。如果找不到这样的节点，说明所有课程都相互依赖，无法开始学习。

然后开始弹出节点，每次弹出节点就从我们的图结构中取出其next节点，即依赖它的节点。将其入度减1.如果其入度 为0，则可以入队。并且加入的结果集中。

如果最终结果集中结果数等于课程数，说明可以完成全部学习。同时结果集中的学习顺序也是可以顺序完成的，不违反依赖的学习顺序。

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //  构建图
        List<Integer>[] graph  = new List[numCourses];
        // 构建入度
        int[] indegress = new int[numCourses];

        for(int i=0;i<numCourses;i++) graph[i] = new ArrayList<>();

        // 填充图，填充入度
        for(int[] prerequisite:prerequisites) {
            // 被依赖指向依赖
            graph[prerequisite[1]].add(prerequisite[0]);
            indegress[prerequisite[0]]++;
        }

        // 构建队列
        Deque<Integer> q = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        // 如果入度为0，入队
        for(int i=0;i<indegress.length;i++) 
        if(indegress[i]==0) {
            q.add(i);
            result.add(i);
        }
        while(!q.isEmpty()) {
            Integer poll = q.poll();
            // 出队代表学习完成，降低依赖它的节点的入度。
            for(Integer next:graph[poll] ) {
                indegress[next]--;
                // 如果依赖它的节点入度为0，入队
                if(indegress[next]==0){
                    q.add(next);
                    result.add(next);
                }
            }
        }
        // 如果最终结果集中结果数等于课程数，说明可以完成全部学习。同时结果集中的学习顺序也是可以顺序完成的，不违反依赖的学习顺序。
        if(result.size()!=numCourses) return new int[]{};
        else {
            int[] ret= new int[numCourses];
            for(int i=0;i<numCourses;i++)ret[i]=result.get(i);
            return ret;
        }
    }
}

ByteDrift

课程表问题

问题背景

思路