题干：

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。 

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。 

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。 

其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。 

Sample Input

4 3
1 2
2 3
4 3

Sample Output

1 2 4 3

解题报告：

    拓扑排序模板。用邻接矩阵存图，会超时。

 

 AC代码：

#include<bits/stdc++.h>

using namespace std;
const int MAX = 500 + 5 ; 
struct Node {
	int to;
	int w;
	int ne;
} e[MAX];
int in[MAX],head[MAX],ans[MAX];
int cnt = 0,top = 0;
priority_queue<int,vector<int > ,greater<int> > pq;
void init() {
	cnt = 0;top = 0;
	memset(in,0,sizeof(in));
	memset(head,-1,sizeof(head));
	while(!pq.empty() ) pq.pop();
}
void add(int u,int v,int w) {
	e[cnt].to = v;
	e[cnt].w = w;
	e[cnt].ne = head[u];
	head[u] = cnt;
	cnt++;  
}
int main()
{
	int n,m;
	int u,v;
	while(~scanf("%d%d",&n,&m) ) {
		init();
		while(m--) {
			scanf("%d%d",&u,&v);
			add(u,v,0);
			in[v]++;
		}
		//预处理一下pq 
		for(int i = 1; i<=n; i++) {
			if(in[i] == 0 ) pq.push(i);
		}
		while(!pq.empty() ) {
			int cur = pq.top();//养成习惯，bfs中也是，取出元素后都先给一个变量cur存着以免以后忘了pop，并且新的都用new表示 
			pq.pop();
			ans[++top] = cur;
			for(int i = head[cur]; i!=-1; i=e[i].ne) {
				in[e[i].to]--;
				if(in[e[i].to] == 0) pq.push(e[i].to);
			}		
		}
		if(top != n ) printf("不成环\n");
		else {
			for(int i = 1; i<=top; i++) {
				printf("%d%c",ans[i],i==top?'\n':' ');
			}
		}
		
	}
	
	return 0 ;
}

超时代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
//struct Edge {
//	int to;
//	int w;
//	int ne;
//	
//} e[5000];
int maze[505][505];
int in[505];
void init() {
	memset(in,0,sizeof(in));
	memset(maze,0,sizeof(maze) ) ;
}
int main()
{
	int n,m,u,v;
	int flag = 0;
	while(~scanf("%d%d",&n,&m) ) {
		init();
		while(m--) {
			scanf("%d%d",&u,&v);
			maze[u][v] = 1;
			in[v]++;
		}
		int cnt = 0 ;
		while(1) {
				
			if(cnt == n) break;
			flag = 0 ;
			for(int i = 1; i<=n; i++) {
				if(in[i] == 0) {
					in[i]--;
					if(cnt == n-1) {
						printf("%d\n",i);
						cnt++;
					}
					for(int j = 1; j<=n; j++) {
						if(maze[i][j] == 1) {
							flag = 1;
							in[j]--;
							maze[i][j] = 0;
							cnt++;
							printf("%d%c",i,cnt==n?'\n':' ');
							break;
						}
					}
					if(flag == 1) {
						break;
					}
				}
			}
			
		}
	}
	return 0 ;
 }