你这个学期必须选修numCourses门课程，记为0到numCourses - 1。
在选修某些课程之前需要一些先修课程。先修课程按数组prerequisites给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程ai则 必须先学习课程bi。
例如，先修课程对[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回true；否则，返回false。
提示：
- 1 <= numCourses <= 10^5
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- prerequisites[i]中的所有课程对互不相同
207.课程表
这种场景很明显用拓扑排序，拓扑排序就是拿来干这活的。
首先记录一个邻接表，同时记录每个节点的入度。对于入度为0的节点，放入队列中。
对于队列中的节点，删除该节点，并将所有与该节点相连的节点入度-1，如果有节点入度减为0，则将该节点加入队列。循环上述过程，直到队列为空。
如果课程表是可行的，那么所有课程都被删除，否则仍存在未被删除的节点。
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
| class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edge(numCourses, vector<int>());
vector<int> indegree(numCourses, 0);
for(const vector<int>& pre : prerequisites){
edge[pre[1]].push_back(pre[0]);
indegree[pre[0]]++;
}
queue<int> q;
int count = 0;
for(int i = 0; i < numCourses; ++i){
if(indegree[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int course = q.front();
q.pop();
count++;
for(int after : edge[course]){
indegree[after]--;
if(indegree[after] == 0){
q.push(after);
}
}
}
return count == numCourses;
}
};
|
类似地，力扣上还有要求输出可行的上课顺序：
210.课程表II
思路是类似的，只是相比起之前删除节点增加计数变成了给答案数组增加元素，不再赘述
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
| class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> edge(numCourses, vector<int>());
vector<int> indegree(numCourses, 0);
for(const vector<int>& info : prerequisites){
edge[info[1]].push_back(info[0]);
indegree[info[0]]++;
}
queue<int> q;
for(int i = 0; i < numCourses; ++i){
if(indegree[i] == 0){
q.push(i);
}
}
vector<int> ans;
while(!q.empty()){
int course = q.front();
q.pop();
ans.push_back(course);
for(int after : edge[course]){
indegree[after]--;
if(indegree[after] == 0){
q.push(after);
}
}
}
return ans.size() == numCourses ? ans : vector<int>();
}
};
|
