程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 210. Course Schedule II(拓撲排序

LeetCode 210. Course Schedule II(拓撲排序

編輯:關於C++

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


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved