题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
1
2
3
| 输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
|
具体见题目描述。
算法思路
这个题目很显然考了拓扑图，对于拓扑结构，可以看这个博客，讲的非常不错，但简要来说，我们可以这么理解，对于一个终点B，其位于路径A->B，则需要到达B，必须先到达A，同理，对于A的一条路径S->A也是一样的，这就是拓扑结构。因此，主要算法如下：
- 对于每个前驱学习关系，采用DFS查看其前驱课程是否已经能够学习，或者是其前驱课程的前驱课程是否能够学习。
- 如果某个课程的所有前驱课程是可以学习的，才认为其可以被学习，否则是不可以被学习的。
可以采用必要的剪枝来避免某些课程重复调用DFS，比如S->A->B->C->D->E->F这个“路径”是可以走通的，那么D->E->F也肯定是可以走通的。代码如下：
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
42
43
44
45
46
47
48
49
| class Solution {
bool PreCanAllLearn(int course) {
for (const int i : PreLearn[course]) {
if (i != -1 && !CanLearn[i]) {
return false;
}
}
return true;
}
bool searchlearnPath(int course) {
if (CanLearn[course]) {
return true;
}
if (PreCanAllLearn(course)) {
CanLearn[course] = 1;
return true;
}
if (find(LearnPath.begin(), LearnPath.end(), course) != LearnPath.end()){
return false;
}
LearnPath.push_back(course);
bool pre_can_learn = true;
for (const int i : PreLearn[course]) {
pre_can_learn = pre_can_learn & searchlearnPath(i);
}
CanLearn[course] = pre_can_learn ? 1 : 0;
return pre_can_learn;
}
public:
vector<int> CanLearn;
vector<vector<int> > PreLearn;
vector<int> LearnPath;
bool canFinish(int numCourses, vector< vector<int> >& prerequisites) {
CanLearn.resize(numCourses, 0);
PreLearn.resize(numCourses);
for (const auto &pre : prerequisites) {
PreLearn[pre[0]].push_back(pre[1]);
}
for (int i = 0; i < prerequisites.size(); i++) {
int res = searchlearnPath(prerequisites[i][0]);
if (!res) {
return false;
}
}
return true;
}
};
|
算法结果如下：
效率上不是很好，因为代码的一些判断（前缀课程是否可以学习）比较耗时，但是他们实际上都是在做一件事：判断某个课程是否可以被学习，但是并不需要区分这个课程是前驱课程还是目标课程，这样的代码不仅更简单，执行效率也高得多，优化后的代码如下：
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
| class Solution {
private:
vector<vector<int>> graph;
vector<int> visited;
bool dfs(int course) {
if (visited[course] == 1) return false;
if (visited[course] == 2) return true;
visited[course] = 1;
for (int pre : graph[course]) {
if (!dfs(pre)) return false;
}
visited[course] = 2;
return true;
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
graph.resize(numCourses);
visited.resize(numCourses, 0);
for (const auto& pre : prerequisites) {
graph[pre[0]].push_back(pre[1]);
}
for (int i = 0; i < numCourses; i++) {
if (!dfs(i)) return false;
}
return true;
}
};
|
代码执行的结果如下：
比刚才的还是好多了，官方题解思路其实差不多，就不再去借鉴了。
