LeetCode 210. Course Schedule II(拓撲排序-求有向圖中是否存在環)

LeetCode 210. Course Schedule II(拓撲排序-求有向圖中是否存在環)

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