LeetCode 210. 课程表 II(拓扑排序)
> m; vector indegree(numCourses, 0); for(auto& pre : prerequisites) { m[pre[1]].insert(pre[0]); indegree[pre[0]]++; } queue q; int tp, finish = 0, i; for(i = 0; i < numCourses; ++i) if(indegree[i] == 0) q.push(i); vector ans(numCourses); i = 0; while(!q.empty()) { tp = q.front(); finish++; ans[i++] = tp; q.pop(); for(auto id : m[tp]) { if(--indegree[id] == 0) q.push(id); } } if(i != numCourses) return { }; return ans; }};
> m; vector ans;public: vector findOrder(int numCourses, vector
发布日期:2021-07-01 03:25:34
浏览次数:2
分类:技术文章
本文共 2486 字,大约阅读时间需要 8 分钟。
1. 题目
现在你总共有 n 门课需要选,记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。
例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序,你只要返回一种就可以了。
如果不可能完成所有课程,返回一个空数组。示例 1:输入: 2, [[1,0]] 输出: [0,1]解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。示例 2:输入: 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] 。 说明:输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。你可以假定输入的先决条件中没有重复的边。提示:这个问题相当于查找一个循环是否存在于有向图中。如果存在循环,则不存在拓扑排序,因此不可能选取所有课程进行学习。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/course-schedule-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
参考:
类似题目:
本题跟 207 题完全一致,只是增加了路径输出。不做过多解释,见207题解答
- DFS的区别是,本题,必须从入度为0的节点开始
2.1 广度优先
class Solution { public: vector findOrder(int numCourses, vector>& prerequisites) { unordered_map
48 ms 14.3 MB
2.2 深度优先
- 需要从入度为0的开始,以便输出顺序
- 结束了要检查路径个数够不够
class Solution { unordered_map
44 ms 14.7 MB
转载地址:https://michael.blog.csdn.net/article/details/106119461 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年05月04日 04时55分01秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
volatile关键字
2019-05-01
Servlet_快速入门
2019-05-01
Request_继承体系
2019-05-01
前端权限控制:获取用户信息接口构造数据
2019-05-01
七牛云存储:断点续传
2019-05-01
字节流复制文本文件【应用】
2019-05-01
字节流复制图片
2019-05-01
私钥加密私钥解密
2019-05-01
锁的释放流程-ReentrantLock.unlock
2019-05-01
Java判断字符串是否为数字(浮点类型也包括)
2019-05-01
ubuntu opencv-python 安装很慢问题
2019-05-01
MySQL5.7版本修改了my.ini配置文件后mysql服务无法启动问题
2019-05-01
【大数据开发】Java基础 -总结21-Hashmap和HashTable的区别
2019-05-01
Azkaban体系结构
2019-05-01
机器学习之重头戏-特征预处理
2019-05-01
synchronized底层实现及锁的升级、降级
2019-05-01
PermGen space-永久区内存溢出
2019-05-01
Maven继承和聚合
2019-05-01