There are a total of n courses you have to take, labeled from 0
to n - 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, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]
. Another correct ordering is[0,2,1,3]
.
Solution 1:
DFS + Topological Sort
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) { vector<list<int>> adj(numCourses, list<int>()); vector<bool> visited(numCourses, false); vector<bool> onstack(numCourses, false); vector<int> order; for(auto& it : prerequisites) { adj[it.second].push_back(it.first); } for(int i=0; i<numCourses; ++i) { if(visited[i]) continue; if(hasCycle(adj, i, visited, onstack, order)) return vector<int>(); } return order; } bool hasCycle(vector<list<int>>& adj, int v, vector<bool>& visited, vector<bool>& onstack, vector<int>& order) { visited[v] = true; onstack[v] = true; for(auto& it : adj[v]) { if(!visited[it] && hasCycle(adj, it, visited, onstack, order)) return true; if(onstack[it]) return true; } order.insert(order.begin(), v); onstack[v] = false; return false; }
Solution 2:
BFS + Topological Sort
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) { vector<list<int>> adj(numCourses, list<int>()); vector<int> requisites(numCourses, 0); vector<int> order(numCourses, 0); queue<int> que; for(auto& it : prerequisites) { adj[it.second].push_back(it.first); requisites[it.first]++; } for(int i=0; i<numCourses; i++) { if(requisites[i]==0) { que.push(i); } } int len = 0; while(!que.empty()) { int course = que.front(); que.pop(); order[len++] = course; for(auto& it : adj[course]) { if(!--requisites[it]) { que.push(it); } } } return len == numCourses ? order : vector<int>(); }
相关推荐
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode1-240题中文题解,md格式,java版本 有题目有题解有代码 需要使用markdown打开
leetcode 1 -200题所有源码 有问题私聊我
本书包含了 LeetCode Online Judge所有题目的答案,所有代码经过精心编写,编码规范良好,适合读者反复揣摩,模仿,甚至在纸上默写
leetcode26 algo 算法与数据结构,练习代码 语言:java 8 开发工具:vscode,安装插件Java Extension Pack vscode有智能提示,可调试,有重构支持,满足代码练习要求,相比IDEA更轻量级,普通笔记本即可流畅运行。 ...
leetcode 答案Leetcode---算法 我对 Leetcode 算法问题的回答