比较标准的一个拓扑排序，因为拓扑排序是不唯一的，此题给了一个限制条件（此时要求输出时编号小的队伍在前），从而使得此结果唯一。

        拓扑排序资料下载>>

//2187595 2010-03-15 17:34:46 Accepted 1285 31MS 312K 998 B C++ 
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

const int N = 502;//每组中的第一行为二个数N（1<=N<=500），

int main()
{
	int n, m, sa, sb;
	int i, j, cc;
	int degree[N];
	vector<int>::iterator p;
	set<int>::iterator sp;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		vector<int> V[N];
		set<int> S;
		memset(degree, 0, (n + 1) * sizeof(int));
		for(i = 0; i < m; i++)
		{
			scanf("%d%d", &sa, &sb);
			degree[sb]++;
			V[sa].push_back(sb);
		}
		for(i = 1; i <= n; i++)
			if(degree[i] == 0)
			{
				S.insert(i);
				degree[i]--;
			}
		i = 0;
		while(!S.empty())
		{
			sp = S.begin();
			cc = *sp;
			S.erase(sp);
			i++;
			if(i != n)
				cout<<cc<<" ";
			else
				cout<<cc<<endl;
			for(p = V[cc].begin(); p != V[cc].end(); p++)
			{
				if(degree[*p] > 0)
				{
					degree[*p]--;
					if(degree[*p] == 0)
					{
						S.insert(*p);
					}
				}
			}
		}

	}
	return 0;
}

• 相关文章
• 全局相关文章