首页 > 编程语言 > 详细

LeetCode 207. Course Schedule(拓扑排序-求有向图中是否存在环)

时间:2015-07-27 18:57:47      阅读:279      评论:0      收藏:0      [点我收藏+]

求有向图中是否有环。


法一:拓扑排序

用一个队列维护所有入度为0的节点,每次弹出一个节点v,查看从v可达的所有节点u;

将u的入读减一,若u的入度此时为0, 则将u加入队列。

在队列为空时,检查所有节点的入度,若所有节点入度都为0, 则存在这样的一个拓扑排序 —— 有向图中不存在环。

代码:

class Solution
{
public:
	bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites)
	{
		vector<vector<bool>> map(numCourses, vector<bool>(numCourses, false));
		vector<int> in_degree(numCourses, 0);
		for_each(prerequisites.begin(), prerequisites.end(),
			[&map, &in_degree](pair<int,int> p)
			{
				if (map[p.first][p.second] == false)
				{
					map[p.first][p.second] = true;
					++ in_degree[p.second];
				}
			});
		queue<int> q;
		for (int id = 0; id < numCourses; ++ id)
		{
			if (in_degree[id] == 0)
			{
				q.push(id);
			}
		}
		while (!q.empty())
		{
			int course = q.front();
			q.pop();
			for (int id = 0; id < numCourses; ++ id)
			{
				if (map[course][id] == true)
				{
					-- in_degree[id];
					if (in_degree[id] == 0)
					{
						q.push(id);
					}
				}
			}
		}
		return all_of(in_degree.begin(), in_degree.end(), [](int in) -> bool
		{
			return in == 0;
		});
	}
};


版权声明:本文为博主原创文章,未经博主允许不得转载。

LeetCode 207. Course Schedule(拓扑排序-求有向图中是否存在环)

原文:http://blog.csdn.net/stephen_wong/article/details/47087613

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!