算法内容
本文件实现 LeetCode 207「课程表」。问题可以转化为判断有向图中是否存在环。
代码使用拓扑排序。m 数组统计每门课的入度，g 存储从先修课程指向后续课程的邻接表。先把所有入度为 0 的课程入栈，然后不断弹出课程并降低后继节点入度；当某个后继入度降为 0 时继续入栈。最后如果存在未访问课程，说明图中有环，无法完成所有课程。时间复杂度 O(V + E)，空间复杂度 O(V + E)。
算法实现
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
| #include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
using namespace std;
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> m(numCourses, 0);
vector<bool> visited(numCourses, false);
unordered_map<int, vector<int>> g;
for(vector<int>& p:prerequisites) {
m[p[0]]++;
g[p[1]].push_back(p[0]);
}
bool find = true;
stack<int> s;
for(int i = 0; i < numCourses; i++) {
if(m[i] == 0) {
s.push(i);
visited[i] = true;
}
}
while(!s.empty()) {
int pos = s.top();
s.pop();
vector<int> arcs = g[pos];
for(int arc : arcs) {
m[arc]--;
if(m[arc] == 0) {
s.push(arc);
visited[arc] = true;
}
}
}
for(bool visit:visited) {
if(!visit) {
return false;
}
}
return true;
}
};
|