题目描述
题目链接:207. Course Schedule
There are a total of
numCourses
courses you have to take, labeled from0
tonumCourses - 1
. You are given an arrayprerequisites
whereprerequisites[i] = [ai, bi]
indicates that you must take coursebi
first if you want to take courseai
.
- For example, the pair
[0, 1]
, indicates that to take course0
you have to first take course1
. Returntrue
if you can finish all courses. Otherwise, returnfalse
.
例子
例子 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.
例子 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
1 <= numCourses <= 10^5
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
- All the pairs
prerequisites[i]
are unique.
解题思路
课与课之间的前置关系可以组成一个或多个树,其中每一条边都是单向边(由当前课指向前置课程),我们要做的是检查树中是否存在环,如果存在则表示出现循环依赖,因此没办法上完所有课。检查是否有环的方法是拓扑排序,如下所示:
#include <vector>
class Solution {
public:
bool canFinish(int numCourses,
std::vector<std::vector<int>>& prerequisites) {
std::vector<std::vector<int>> hmap(numCourses);
std::vector<int> status(numCourses, 0);
for (auto preq : prerequisites) {
hmap[preq[0]].push_back(preq[1]);
}
for (int i = 0; i < numCourses; ++i) {
if (!dfs(hmap, status, i)) {
return false;
}
}
return true;
}
private:
bool dfs(const std::vector<std::vector<int>>& hmap,
std::vector<int>& status, int current_course) {
for (int preq : hmap[current_course]) {
if (status[preq] == 1) {
continue;
} else if (status[preq] == -1) {
return false;
} else {
status[preq] = -1;
if (!dfs(hmap, status, preq)) {
return false;
}
status[preq] = 1;
}
}
return true;
}
};
- 时间复杂度:
O(|E|)
- 空间复杂度:
O(max(|E|, |V|))
GitHub 代码同步地址: 207.CourseSchedule.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions