和LeetCode 207. Course Schedule(拓扑排序-求有向图中是否存在环)类似。
?
注意到，在for (auto p: prerequistites)中特判了输入中可能出现的平行边或自环。
?
代码：
?
class Solution
{
public:
vector
findOrder(int numCourses, vector
>& prerequisites) { // [0, {1, 2, 3}], means after finishing #0, you might be able to take #1, #2, #3 // That is, you must finish #0, before trying to take #1, #2, #3 map
> course_chain; vector
in_degree(numCourses, 0); queue
q; vector
ret; for (auto p: prerequisites) { // self-loop, return empty vector. if (p.first == p.second) { return vector
(); } // no duplicate edges input if (find(course_chain[p.second].begin(), course_chain[p.second].end(), p.first) == course_chain[p.second].end()) { course_chain[p.second].push_back(p.first); ++ in_degree[p.first]; } } for (size_t i = 0; i < numCourses; ++ i) { if (in_degree[i] == 0) { q.push(i); } } for (; !q.empty(); q.pop()) { int pre_course = q.front(); ret.push_back(pre_course); for (auto it = course_chain[pre_course].begin(); it != course_chain[pre_course].end(); ++ it) { -- in_degree[*it]; if (in_degree[*it] == 0) { q.push(*it); } } } return ret.size()==numCourses? ret: vector
(); } };
?