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.
For example:
2, [[1,0]]
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]
4, [[1,0],[2,0],[3,1],[3,2]]
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.
題意
共有n節(jié)課程，課程編號從0至n－1。一些課程可能有先修要求，比如修0號課程前需要先修1號課程，表示為［0,1］蔼两。題目給出課程數(shù)和先后修課程對，要求返回完成所有課程的順序∷憷可能有很多正確的上課順序，你只需返回其中一種泳姐。如果不可能完成效拭，則返回空數(shù)組。
比如：
2, [[1,0]]
共有2節(jié)課程。選修1號課程前需要先修0號課程缎患，故上課順序?yàn)?code>[0,1]慕的。
4, [[1,0],[2,0],[3,1],[3,2]]
共有4節(jié)課程。正確的上課順序?yàn)?code>[0,2,1,3]挤渔。
提示：
輸入的prerequisites是由邊表示的圖肮街，而非鄰接矩陣。
分析
此題是Leetcode207-Course Schedule的進(jìn)階版判导，前者只需得出能否完成所有課程即可嫉父，本題還需要給出上課順序。實(shí)際上這是一個求拓?fù)渑判虻念}（至于是拓?fù)淙蜻€是拓?fù)淦蜓廴校遣灰欢ǖ模┤葡健？梢杂?種求解方法擂红。
第一種：采用bfs仪际。前處理時得到每個節(jié)點(diǎn)的入度。每次將入度為0的節(jié)點(diǎn)入隊(duì)昵骤。出隊(duì)時將出隊(duì)節(jié)點(diǎn)的鄰接節(jié)點(diǎn)的入度減1树碱，并將出隊(duì)節(jié)點(diǎn)編號計(jì)入answer數(shù)組中。循環(huán)該過程直到隊(duì)列為空变秦。如仍有節(jié)點(diǎn)未被訪問成榜，則說明課程關(guān)系圖中出現(xiàn)了環(huán)，不可能完成所有課程伴栓。否則伦连，answer中的編號順序就是上課順序。
第二種：采用dfs钳垮。需要一個onStack數(shù)組紀(jì)錄dfs的路徑上的節(jié)點(diǎn)惑淳，用于判斷環(huán)的存在。而isVisited數(shù)組責(zé)紀(jì)錄dfs中訪問過的節(jié)點(diǎn)饺窿。而其reversePostOrder就是上課順序歧焦。具體可以google搜索reversePostOrder。這種方法比較難理解肚医，但很有意思绢馍。最終給出的AC代碼也是第二種方法。
注意
值得注意的是肠套，特殊情況輸入numCourses ＝ 1舰涌，prereqisities為空數(shù)組時，答案為
[0]你稚，只有1個節(jié)點(diǎn)瓷耙，并沒有邊的存在朱躺。第二種方法中onStack在每次結(jié)束本次遞歸時，需要變?yōu)閒alse搁痛，表示這條路徑上后面的節(jié)點(diǎn)在后面的判斷環(huán)中长搀，不會被認(rèn)為是同一路徑上的節(jié)點(diǎn)。（感覺好繞）
AC代碼
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> answer;
if (numCourses == 1) {
answer.push_back(0); return answer;
}
vector<vector<int>> map(numCourses, vector<int>());
stack<int> reversePostOrder;
for (int i = 0; i < prerequisites.size(); ++i) {
map[prerequisites[i].second].push_back(prerequisites[i].first);
}
vector<bool> isVisited(numCourses, false);
for (int i = 0; i < numCourses; ++i) {
if (!isVisited[i]) {
vector<bool> onStack(numCourses, false);
if (hasCycle(map, i, isVisited, onStack, reversePostOrder))
return answer;
}
}
while (!reversePostOrder.empty()) {
int index = reversePostOrder.top(); reversePostOrder.pop();
answer.push_back(index);
}
return answer;
}
bool hasCycle(vector<vector<int>> &map, int i, vector<bool> &isVisited, vector<bool> &onStack, stack<int> &reversePostOrder) {
isVisited[i] = true;
onStack[i] = true;
for (int k : map[i]) {
if (onStack[k])
return true;
else if (!isVisited[k])
if (hasCycle(map, k, isVisited, onStack, reversePostOrder))
return true;
}
onStack[i] = false;
reversePostOrder.push(i);
return false;
}
};
