题目描述
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example1:
Input: 2, [[1,0]] Output: [0,1] Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .
Example2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
NOTE
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
解题思路
- 首先要知道如何表示图 可以用一个二维数组来进行 [1, 0]表示以节点0 指向 节点1 即在数据中可以存 graph[a[1]].push_back(a[0]) // 表示 a0 -> a1
- 然后还要知道如何表示入度节点 in[num] // num 为节点的个数
- BFS宽度优先搜索
- 我们遍历总得节点，将节点 如果入度为0，则直接push到节点数组中就可以 // 如果这一步，没有找到度数为0的节点，证明这个图中存在环，返回空即可
- 然后根据这个队列中的元素，去图中找以此为被指向的节点，并且将这些被指向的节点的入度进行减少，如果减少到0
- 需要将其push到结果数组中
- push到入度为0的队列中
- 最后将结果数组与节点的个数相对比，如果不等，返回NULL即可
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses, vector<int>());
vector<int> in(numCourses);
for(auto& a : prerequisites){
graph[a[1]].push_back(a[0]);
in[a[0]]++;
}
queue<int> q;
vector<int> res;
for(int i = 0; i < numCourses; i++){
if(in[i] == 0){
q.push(i);
res.push_back(i);
}
}
if(q.empty() == true){
return {};
}
while(!q.empty()){
int t = q.front();
q.pop();
for(auto& a : graph[t]){
--in[a];
if(in[a] == 0){
q.push(a);
res.push_back(a);
}
}
}
if(res.size() != numCourses){
return {};
}
return res;
}
};
