0%

[Leetcode]207. Course Schedule(C++)

题目描述

题目链接:207. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
    Return true if you can finish all courses. Otherwise, return false.

例子

例子 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.

解题思路

课与课之间的前置关系可以组成一个或多个树,其中每一条边都是单向边(由当前课指向前置课程),我们要做的是检查树中是否存在环,如果存在则表示出现循环依赖,因此没办法上完所有课。检查是否有环的方法是拓扑排序,如下所示:

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
#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