210. 課程表 II - 力扣（LeetCode）

這是一道拓撲排序的模板題。簡單來說，給出一個有向圖，把這個有向圖轉成線性的排序就叫拓撲排序。如果有向圖中有環就沒有辦法進行拓撲排序了。因此，拓撲排序也是圖論中判斷有向無環圖的方法。

用bfs的拓撲排序思路如下：1.找到入度為0的節點，加入結果集；2.將該節點從圖中移除

需要注意三點：1.移除不是真的移除，只不過是把與這個節點相連的節點的入度減一；2.如果一個節點與兩個或以上個節點相連，那么在移除了這個節點之后就會有多個選擇，因此拓撲排序的結果不唯一；3.如果結果集的元素個數不等于圖中節點個數，那么就必定有環。

class Solution 
{
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {int n=numCourses;vector<vector<int>>graph(n);//圖vector<int>ans;//結果集vector<int>inDegree(n,0);//記錄入度的數組for(auto&p:prerequisites)//構建圖{graph[p[1]].push_back(p[0]);inDegree[p[0]]++;}queue<int>que;for(int i=0;i<n;i++)//將入度為0的節點加入隊列{if(inDegree[i]==0){que.push(i);}}while(!que.empty()){int fro=que.front();que.pop();ans.push_back(fro);//加入結果集for(int x:graph[fro])//處理節點fro指向的節點{inDegree[x]--;if(inDegree[x]==0){que.push(x);}}}if(ans.size()!=n){return {};}return ans;}
};