-
Notifications
You must be signed in to change notification settings - Fork 0
/
210.findOrder2.cpp
49 lines (44 loc) · 1.26 KB
/
210.findOrder2.cpp
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 {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
int N = prerequisites.size() + numCourses;
// int N = 10010;
if(!N) return {};
int idx = 0, e[N], h[N], ne[N];
memset(e, 0, sizeof e);
memset(h, -1, sizeof h);
memset(ne, 0, sizeof ne);
int q[N], d[numCourses];
memset(q, 0, sizeof q);
memset(d, 0, sizeof d);
// 初始化数据
for(int i = 0; i < prerequisites.size(); i++){
e[idx] = prerequisites[i][0];
ne[idx] = h[prerequisites[i][1]];
h[prerequisites[i][1]] = idx++;
d[prerequisites[i][0]]++;
}
// 拓扑排序
int hh = 0, tt = -1;
for(int i = 0; i < numCourses; i++){
if(d[i] == 0){
q[++tt] = i;
}
}
while(hh <= tt){
int u = q[hh++];
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(--d[j] == 0){
q[++tt] = j;
}
}
}
// 输出结果
if(tt == numCourses-1){
return vector<int>(q, q+tt+1);
}else{
return {};
}
}
};