LN : leetcode 207 Course Schedule
2024-08-30 23:39:27
lc 207 Course Schedule
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, is it possible for you to finish all courses?
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 it is possible.
2, [[1,0],[0,1]]
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.
DFS Accepted##
这是一个非常典型的拓扑排序问题,整个问题可以总结为如何判断有向图是否有环。通过对图上的每一个点做DFS,如果都是无环的,则能证明课程安排是合理的。注意,点的状态有三种,分别是没被访问,第一次访问后以及第二次访问后。
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<set<int>> graph(numCourses);
bool cycle = false;
for (auto prev : prerequisites) {
graph[prev.second].insert(prev.first);
}
vector<int> visited(numCourses, 0);
for (int i = 0; i < numCourses; i++) {
if (cycle) return false;
if (visited[i] == 0) dfs(i, graph, visited, cycle);
}
return !cycle;
}
void dfs(int nodei, vector<set<int>> &graph, vector<int> &visited, bool &cycle) {
if (visited[nodei] == 1) {
cycle = true;
return;
}
visited[nodei] = true;
for (auto i : graph[nodei]) {
dfs(i, graph, visited, cycle);
if (cycle) return;
}
visited[nodei] = 2;
}
};
最新文章
- React学习笔记-1-什么是react,react环境搭建以及第一个react实例
- 如何在centos 6.7 上安装oracle 11gR2
- Runtime 方法替换 和 动态添加实例方法 结合使用
- 基于IHttpAsyncHandler的实时大文件传送器
- 网站瓶颈分析—MYSQL性能分析
- .net类库中和数据库相关的
- how to install flash
- MVC三个IOC注入点之Ninject使用示例
- POJ 2481-Cows(BIT)
- [liu yanling]常用的测试工具
- PHP使用IP地址连接MySQL数据库
- cxf WebService整理 (基于注解)
- 关于Tcp三次握手的思考
- Godiva_百度百科
- Linux下df与du两个命令的差别?
- Redis 学习(一) —— 安装、通用key操作命令
- python2和3的区别
- axios的秘密
- JavaScript中的可枚举属性与不可枚举属性
- Poj2010 Moo University - Financial Aid
热门文章
- Java的文件注释
- openstack setup demo Compute service
- Utuntu下Xshell使用+vi使用
- 浅谈cookie,sessionStorage和localStorage区别
- myEclipse怎样将程序部署到tomcat(附录MyEclipse调试快捷键)
- Android学习笔记之Spinner下拉列表使用案例
- [swift实战入门]手把手教你编写2048(一)
- SUSE Linux源代码编译安装MySQL 5.6
- Spark技术内幕:Master基于ZooKeeper的High Availability(HA)源代码实现
- mysql对表列数和行大小的限制