HDU 1285-确定比赛名次 ( 拓扑排序）

HDU 1285-确定比赛名次 ( 拓扑排序）

题意：给若干比赛结果，按字典序输出比赛排名

思路：拓扑排序，利用BFS建立结点关系。

时间复杂度：O(V+E)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e2+5;
int in[N],n,m,u,v,now;
int g[N][N];
#define mst(a) memset(a,0,sizeof a)
void toposort(){//拓扑排序 
	priority_queue<int,vector<int>,greater<int> >q;//优先队列输出最小编号 
	for(int i=1;i<=n;i++) if(!in[i]) q.push(i);//入度为0的点入队 
	int c=1;//控制输出格式 
	while(q.size()){
		now=q.top();q.pop();
		if(c!=n) printf("%d ",now),c++;
		else printf("%d\n",now);
		for(int i=1;i<=n;i++)
			if(g[now][i]) //相邻点入度减1 
			{
				in[i]--;
				if(!in[i]) q.push(i);
			} 
	} 
}
int main(){
	while(cin>>n>>m){
		mst(in),mst(g);//初始化 
		while(m--){
			cin>>u>>v;
			if(!g[u][v])//防止重边影响入度. 
			g[u][v]=1,in[v]++;
		}
		toposort();
	}
	return 0;
}