UVa10305 - Ordering Tasks

题目地址：点击打开链接

拓扑排序

#include <iostream>
#include <deque>
#include <cstring>
#include <vector>
using namespace std;
const int maxsize = 110;
int graph[maxsize][maxsize];
int inDegree[maxsize];
int main()
{
	int n,m;
	while(cin>>n>>m&&(n||m))
	{
		memset(graph,0,sizeof(graph));
		memset(inDegree,0,sizeof(inDegree));
		int i;
		for(i=0;i<m;++i)
		{
			int a,b;
			cin>>a>>b;
			graph[a][b]=1;
			++inDegree[b];
		}
		deque<int> di;
		for(i=1;i<=n;++i)
		{
			if(inDegree[i]==0)
				di.push_back(i);
		}
		vector<int> p;
		while(!di.empty())
		{
			int x=di.front();
			di.pop_front();
			p.push_back(x);
			for(i=1;i<=n;++i)
			{
				if(graph[x][i]!=0)
				{
					graph[x][i]=0;
					if(--inDegree[i]==0)
						di.push_back(i);
				}
			}
		}
		for(i=0;i<p.size()-1;++i)
			cout<<p[i]<<" ";
		cout<<p[i]<<endl;
	}
	return 0;
}

UVa10305 - Ordering Tasks,布布扣,bubuko.com

UVa10305 - Ordering Tasks

原文：http://blog.csdn.net/leizh007/article/details/21991603