GuilinDev

Lc0207

05 August 2008

207 Course Schedule

原题

There are a total of ‘numCourses’ courses you have to take, labeled from ‘0’ to ‘numCourses-1’.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: ‘[0,1]’

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• ‘1 <= numCourses <= 10^5’

分析

这种有前置条件的题目要养成思维，这道题可以简化成： 课程安排图是否可以称为 有向无环图(Directed Acyclic Graph, DAG)，即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。

思路：通过拓扑排序判断此课程安排图是否是 有向无环图(DAG) 。 拓扑排序原理： 对 DAG 的顶点进行排序，使得对每一条有向边 (u, v)，均有 u（在排序记录中）比 v 先出现。亦可理解为对某点 v 而言，只有当 v 的所有源点均出现了，v 才能出现。

通过课程前置条件列表 ‘prerequisites’ 可以得到课程安排图的 邻接表 ‘adjacency’，以降低算法时间复杂度，以下两种方法都会用到邻接表。

代码

方法1 - BFS (in-degree table)

1. 统计课程安排图中每个节点的入度，生成 入度表 ‘indegrees’。
2. 借助一个队列 ‘queue’，将所有入度为 0 的节点入队（indegree为0说明是没有前置条件的课程）。
3. 当 ‘queue’ 非空时，依次将队首节点出队，在课程安排图中删除此节点 ‘pre’：
4. 并不是真正从邻接表中删除此节点 ‘pre’，而是将此节点对应所有邻接节点 ‘cur’ 的入度 -1，即 ‘indegrees[cur] -= 1’。
5. 当入度 -1后邻接节点 ‘cur’ 的入度为 0，说明 ‘cur’ 所有的前驱节点已经被 “删除”，此时将 ‘cur’ 入队
6. 在每次 ‘pre’ 出队时，执行 ‘numCourses–’
7. 若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。换个角度说，若课程安排图中存在环，一定有节点的入度始终不为 0。
8. 因此，拓扑排序出队次数等于课程个数，返回 ‘numCourses == 0’ 判断课程是否可以成功安排。

时间复杂度 O(N + M)： 遍历一个图需要访问所有节点和所有临边，N 和 M 分别为节点数量和临边数量；

空间复杂度 O(N + M)： 为建立邻接表所需额外空间，adjacency 长度为 N ，并存储 MM条临边的数据。

用一个HashMap来记录依赖的出度课程，这个是背诵模板

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // HashMap来记录课程和该课程的出度课程的顶点
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>();
        // 数组记录每个课程的入度
        int[] inDegrees = new int[numCourses];
        
        for (int[] pre : prerequisites) {
            inDegrees[pre[0]]++;
            // key - 课程 
            // value - 依赖该课程的别的课程
            map.computeIfAbsent(pre[1], k -> new HashSet<>()).add(pre[0]);
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        // 找到入度为0的课程，也就是不依赖别的课程的课程
        for (int i = 0; i < numCourses; i++) {
            if (inDegrees[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int currCourse = queue.poll();            
            numCourses--;
            
            // 独立的课程，虽然入度为0，但跟任何别的课程没有联系
            // 即没通过prerequisites关系存入到map中的那些课程
            if (!map.containsKey(currCourse)) {
                continue;
            }
            
            for (int followingCourse : map.get(currCourse)) {
                inDegrees[followingCourse]--; // 修掉key先修课程，依次给value课程减掉一次依赖
                if (inDegrees[followingCourse] == 0) { // value课程没有先修课程了，否则，则需要先上另外的先修课程
                    queue.offer(followingCourse); // value课程可能是别的课程的先修课程
                }
            }
        }
        return numCourses == 0;
    }
}

用邻接表

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses]; // 入度表
        List<List<Integer>> adjacency = new ArrayList<>(); //邻接表存储图
        
        //BFS
        Queue<Integer> queue = new LinkedList<>();
        
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        
        // 给每门课添加入度，以及将入度信息和课程本身添加到邻接表中
        for (int[] pre : prerequisites) {
            indegrees[pre[0]]++;
            adjacency.get(pre[1]).add(pre[0]);
        }
        
        // 将入度为0（没有前置课程的）的课程索引初始化入队
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }
        
        // BFS拓扑排序
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for (int cur : adjacency.get(pre)) { // 当前课程减去入度
                indegrees[cur]--;
                if (indegrees[cur] == 0) {
                    queue.offer(cur);
                }
            }
        }
        return numCourses == 0;
    }
}

因为课程是数字来表示，所以可以不用邻接表来存储每个入度，直接相加即可

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] results = new int[numCourses];
        int[] indegrees = new int[numCourses]; //入度表也可以用hashmap表示

        // 创建入度表
        for (int[] pre : prerequisites) {
            indegrees[pre[0]]++; // 把每个入度简化为增加1
        }

        Queue<Integer> queue = new ArrayDeque<>();
        // 首先将入度为0的顶点放进来
        for (int i = 0; i < numCourses; i++) { // 课程表用数字表示
            if (indegrees[i] == 0) {
                queue.offer(i);
            } 
        }

        int count = 0; // 记录课程是否全部被修完
        while (!queue.isEmpty()) {
            int currCourse = queue.poll();
            results[count] = currCourse; // 把访问到的顶点（修完的课）加入到结果中
            count++;

            // 更新剩余未访问的顶点（未修的课）的入度，并将入度为0的课加入到队列中准备访问
            for (int[] pre : prerequisites) {
                if (pre[1] == currCourse) { // 只用修改依赖课程是当前课程的课程
                    indegrees[pre[0]]--; // 依赖课程是当前课程的课程的入度--11
                    if (indegrees[pre[0]] == 0) { // 入度为0则将课程加入到BFS的下一层中
                        queue.offer(pre[0]); 
                    }
                }
            }
        }

        // 检查下全部课程是否都被修完
        return count == numCourses;
    }
}

方法2 - DFS，通过 DFS 判断图中是否有环。

1. 借助一个标志列表 ‘flags’，用于判断每个节点 ‘i’ （课程）的状态：
   1. 未被 DFS 访问：’i == 0’
   2. 已被当前节点启动的 DFS 访问：’i == 1’
   3. 之前已被其他节点启动的 DFS 访问：’i == -1’
2. 对 ‘numCourses’ 个节点依次执行 DFS，判断每个节点起步 DFS 是否存在环，若存在环直接返回 False。DFS 流程:
3. 终止条件：
   • 当 ‘flag[i] == -1’，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回true
   • 当 ‘flag[i] == 1’，说明在本轮 DFS 搜索中节点 ‘i’ 被第 22 次访问，即 课程安排图有环 ，直接返回false
4. 将当前访问节点 ‘i’ 对应 ‘flag[i]’ 置为 1，即标记其被本轮 DFS 当前节点访问过
5. 递归访问当前节点 ‘i’ 的所有邻接节点 ‘j’，当发现环直接返回false
6. 当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点 ‘flag’ 置为 -1并返回true （下面的DFS表示已被之前节点访问过）
7. 若整个图 DFS 结束并未发现环，返回 true，否则返回false。

时间复杂度 O(N + M)： 遍历一个图需要访问所有节点和所有临边，N和 M分别为节点数量和临边数量；

空间复杂度 O(N + M)： 为建立邻接表所需额外空间，adjacency 长度为 N ，并存储 M 条临边的数据。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();// 邻接表存储图
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new ArrayList<>());
        }
        
        int[] flags = new int[numCourses];
        
        for (int[] pre : prerequisites) {
            adjacency.get(pre[1]).add(pre[0]);
        }
        
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(adjacency, flags, i)) {
                return false;
            }
        }
        return true;
    }
    
    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if (flags[i] == 1) {
            return false;
        }
        if (flags[i] == -1) {
            return true;
        }
        flags[i] = 1;
        for (int j : adjacency.get(i)) {
            if (!dfs(adjacency, flags, j)) {
                return false;
            }
        }
        flags[i] = -1;
        return true;
    }
} 

This site is open source. Improve this page.