题目链接：

Problem Description

有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

代码例如以下：

一、（直接法）

#include 
     
      #include 
      
       #define MAXN 517int G[MAXN][MAXN];//路径int in_degree[MAXN];//入度int ans[MAXN];int n, m, x, y;int i, j;void toposort(){	for(i = 1; i <= n; i++)	{		for(j = 1; j <= n; j++)		{			if(G[i][j])			{				in_degree[j]++;			}		}	}	for(i = 1; i <= n; i++)//从最小的開始寻找。	{//这样保证了有多个答案时序号小的先输出		int k = 1;		while(in_degree[k] != 0)//寻找入度为零的点			k++;		ans[i] = k;		in_degree[k] = -1;		//更新为-1。后边检測不受影响，相当于删除节点		for(int j = 1; j <= n; j++)		{			if(G[k][j])				in_degree[j]--;//相关联的入度减1		}	}}void init(){	memset(in_degree,0,sizeof(in_degree));	memset(ans,0,sizeof(ans));	memset(G,0,sizeof(G));}int main(){	while(~scanf("%d%d",&n,&m))	{		init();		for(i = 0; i < m; i++)		{			scanf("%d%d",&x,&y);			G[x][y] = 1;		}		toposort();		for(i = 1; i < n; i++)			printf("%d ",ans[i]);		printf("%d\n",ans[n]);	}	return 0;}
      
     

二、拓扑排序+优先队列：

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;bool map[517][517];int in[517];priority_queue
         
          
           ,greater
           
             > q;void topo(int n){ for(int i=1;i<=n;i++) { if(in[i]==0) q.push(i); } int c=1; while(!q.empty()) { int v=q.top(); q.pop(); if(c!=n) { cout<
            
             <<" "; c++; } else cout<
             
              <
              
               >n>>m) { int k=0; memset(map,0,sizeof map); memset(in,0,sizeof in); while(m--) { cin>>i>>j; if(map[i][j]) continue; map[i][j]=1; in[j]++; } topo(n); }}
              
             
            
           
          
         
        
       
      
     

三、邻接表+拓扑排序：

①：数组式邻接表：

代码例如以下：

#include 
     
      using namespace std;int ind[517];       // indegree入度个数int adj[250017];    //adjacency list邻接表位置值int adj_next[250017];//邻接表下一指针int tail[517];      //邻接表尾int main(){    int n,m,i,j,a,b;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i = 0; i <= n; i++) 		{             tail[i] = -1;            adj[i] = -1;            adj_next[i] = -1;            ind[i] = 0;        }        for(i = 0; i < m; ++i)        {            scanf("%d%d",&a,&b);            int x = tail[a],flag = 0;            while(x != -1)  //推断是否重边            {                if(adj[x] == b)				{                    flag = 1;                    break;                }                x = adj_next[x];            }            if(!flag)//关联a的邻接表            {                adj[i] = b;                adj_next[i] = tail[a];                tail[a] = i;                ind[b] ++;            }        }        for(i = 1;i <= n; i++)//找n次        {            for(j = 1;j <= n;j++)//遍历            {                if(ind[j] == 0)//当入度为0时，说明靠前				{					ind[j] = -1;//在下次寻找入度为0时跳过                    if(i == 1)  						printf("%d",j);                    else       						printf(" %d",j);                    for(int k = tail[j]; k != -1; k = adj_next[k])//邻接位置入度减一                    {                        ind[adj[k]]--;                    }                    break;                }            }        }        printf("\n");    }    return 0;}
     

②：结构体（链表）式邻接表：

代码例如以下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define maxn 517struct node{ int num; node *next;};node map[maxn];int d[maxn], n;void Insert(int a, int b);void Free();void Topsort();int main(){ int m; while(cin >> n >> m) { int i, a, b; memset(d, 0, sizeof(d)); for(i=0; i
            
             > a >> b; Insert(a, b); d[b]++; } Topsort(); Free(); } return 0;}void Insert(int a, int b){ node *newnode; newnode = (node *)malloc(sizeof(node)); newnode->num = b; newnode->next = map[a].next; map[a].next = newnode;}void Free(){ node *cur, *old; for(int i=1; i<=n; i++) { cur = map[i].next; while(cur) { old = cur; cur = cur->next; free(old); } map[i].next = NULL; }}void Topsort(){ priority_queue
             

, greater

> que; int nx, i; int q[maxn]={0}, k=0; node *cur; for(i=1; i<=n; i++) { if(d[i] == 0) que.push(i); } while(que.size()) { nx = que.top(), que.pop(); q[k++] = nx; cur = map[nx].next; while(cur) { nx = cur->num; d[nx] -= 1; if(d[nx] == 0) que.push(nx); cur = cur->next; } } cout << q[0]; for(i=1; i