Keshawn_lu's Blog

Leetcode 210. 课程表 II

图
字数统计: 1.1k阅读时长: 4 min
2020/05/17 Share

题目简介：

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

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

示例 1:

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

示例 2:

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

说明:

  1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

提示:

  1. 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。

  2. 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。

  3. 拓扑排序也可以通过 BFS 完成。

思路：

这是一道拓扑排序的题，首先我们把每一门课看成一个节点，若在学习 A 课程之前必须完成课程 B ，则从 B 到 A 连接一条有向边，这样在拓扑排序中，B 一定出现在 A 的前面。

我们使用广度优先搜索，定义一个队列，首先将入度为0的顶点入队(即没有先修课程的限制)。当我们将队头的节点出队后(即存入答案)，就可以移除它的所有出边，代表着它的相邻节点少了一门先修课程的要求，这样循环直至队列为空。

若最后的答案包含了这n个结点，则找到了一种拓扑排序；否则图中存在环(存在无法入队的顶点)，即不存在拓扑排序。

tips:

  • 给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：

对于图 G 中的任意一条有向边 (u,v)，u 在排列中都出现在 v 的前面。

​ 那么称该排列是图 G 的「拓扑排序」。

  • 如果图 G 中存在环（即图 G 不是「有向无环图」），那么图 G 不存在拓扑排序。这是因为假设图中存在环$x{1},x{2},…,x{n},x{1}$，那么$x{1}$在排列中必须出现在$x{n}$的前面，但$x{n}$同时也必须出现在$x{1}$的前面，因此不存在一个满足要求的排列，也就不存在拓扑排序；

  • 如果图 G 是有向无环图，那么它的拓扑排序可能不止一种。举一个最极端的例子，如果图 G 值包含 n 个节点却没有任何边，那么任意一种编号的排列都可以作为拓扑排序。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:

    vector<vector<int>> edges;  //存储图的边，edges[0][1]代表从0到1的边
    vector<int> indegree;   //存储每个节点的入度

    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){

        vector<int> res;
        edges.resize(numCourses);
        indegree.resize(numCourses);    //resize，默认元素都为0

        for(auto info : prerequisites){

            edges[info[1]].push_back(info[0]);  //从info[1]到info[0]的边
            indegree[info[0]]++;    //info[0]入度+1;
        }

        queue<int> q;
        for(int i = 0; i < indegree.size(); i++){

            if(indegree[i] == 0)
                q.push(i);    //将入度为0的点入队
        }

        while(!q.empty()){

            int node_start = q.front();
            q.pop();    //取出队头元素
            res.push_back(node_start);   //放入答案

            for(int node_end : edges[node_start]){
                indegree[node_end]--;   //相应的节点入度减一
                if(indegree[node_end] == 0)
                    q.push(node_end);
            }
        }

        if(res.size() != numCourses)
            return {};  //不存在拓扑排序
        else
            return res;

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网