世间无限丹青手
一片伤心画不成
拓扑排序，这题今年春招实习两次面到，一次wxg，一次阿里云，不过最后都没去2333。
第一次见到这道题，是2018年准备保研的时候，刷PAT甲级刷到的，反正当时都是做不出来的，都得看别人的题解才能想到这个道题是拓扑排序。
当然这道题也不是直接拓扑排序，需要先建立有向图。有向图可以用二维数组，也可以用邻接表，这个看个人喜好了。
简单讲下步骤：
- 建立有向图（邻接表），同时创建入度的数组
- 将入度数组中入度为0的下标放入到队列里
- BFS遍历图，从队列中取出入度为0的顶点，并输出。每次走相邻顶点的时候，将邻点的入度减一，入度为0的点继续放入队列
需要注意的就是图可能不是连通的，存在不能全部遍历的情况，这时候输出空数组。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> g(numCourses);
vector<int> in_du(numCourses);
for (const vector<int> it : prerequisites) {
int b = it[0], a = it[1];
in_du[b]++;
g[a].emplace_back(b);
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (in_du[i] == 0) q.push(i);
}
vector<int> ans;
while (!q.empty()) {
int now = q.front();
q.pop();
ans.emplace_back(now);
for (const int next : g[now]) {
in_du[next]--;
if (in_du[next] == 0) q.push(next);
}
}
if (ans.size() == numCourses)
return ans;
else return vector<int> ();
}
};
