[数据结构与算法]HDU1285确定比赛名次（拓扑排序+优先队列）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1285

思路

每场比赛的结果我们可以看成一个有向图，从胜利的一方指向失败的一方，在这个有向图的入度为0的点就是最外层不能确定排名的点，然后我们按照编号从小到大排序，将这些点保存在ans中，然后我们将这些点的出度全部清空，然后再看下一层，这其实就是拓扑排序啦，只不过我们需要保证排名不唯一的情况下先输出编号小的队伍，那么我们可以用优先队列来维护这个拓扑排序，更多详情请看代码哦

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f

const int N = 5e2+10;

int n,m;
int du[N];

vector<int> E[N];

void topsort(){
	vector<int> ans;
	priority_queue<int,vector<int>,greater<int> > que;
	for(int i = 1;i <= n; ++i) 
		if(!du[i]) que.push(i);
	
	while(!que.empty()){
		int t = que.top();
		que.pop();
		ans.push_back(t);
		for(int i = 0,l = E[t].size();i < l; ++i) {
			int v = E[t][i];
			du[v]--;
			if(!du[v]) que.push(v);
		}
	}
	for(int i = 0;i < n; ++i)
		cout<<ans[i]<<" \n"[i == n-1];
}


int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	while(cin>>n>>m){
		for(int i = 0;i <= n; ++i) 
			E[i].clear(),du[i] = 0;
		int u,v;
		for(int i = 1;i <= m; ++i) {
			cin>>u>>v;
			du[v]++;
			E[u].push_back(v);
		}
		topsort();
	}
	return 0;
}