和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
         
          (); } };
         
        
       
      
     
    
   
  

?