杭电 1285 确定比赛名次（直接拓扑排序）

绝地灬酷狼 2021-12-20 08:55 189阅读 0赞

## 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

[**拓扑排序模板链接**][Link 1]

**核心：记录前驱为0的，删除以 前驱为0的点 为尾的箭头**

二维数组记录

1 #include<cstdio>
     2 #include<string.h>
     3 int n,m,i,j,num[505],que[505],map[505][505];
     4 void topo()
     5 {
     6     int i,j;
     7     int k=0;
     8     for(i = 1 ; i <= n ; i++)
     9     {
    10         for(j = 1 ; j <= n ; j++)
    11         {
    12             if(num[j] == 0)
    13             {
    14                 m=j;
    15                 break;
    16             }
    17         }
    18         que[k++]=m;
    19         num[m]=-1;
    20         for(j = 1 ; j <= n ; j++)
    21         {
    22             if(map[m][j])
    23             {
    24                 num[j]--;
    25             }
    26         }
    27     }
    28     for(i = 0 ; i < k ; i++)
    29     {
    30         printf("%d",que[i]);
    31         if(i != k-1)
    32             printf(" ");
    33         else
    34             printf("\n");
    35     }
    36     
    37 }
    38 int main()
    39 {
    40     while(scanf("%d %d",&n,&m)!=EOF)
    41     {
    42         int a,b;
    43         memset(map,0,sizeof(map));
    44         memset(num,0,sizeof(num));
    45         for(i = 0 ; i < m ; i++)
    46         {
    47             scanf("%d %d",&a,&b);
    48             if(map[a][b]==0)
    49             {
    50                 map[a][b]=1;
    51                 num[b]++;
    52             }
    53         }
    54         topo();
    55     }
    56 }

邻链表记录

1 #include<cstdio>
     2 #include<string.h>
     3 int n,m,i,j,a,b,que[505],num[505],head[505];
     4 struct stu
     5 {
     6     int to,next;
     7 }st[100000];
     8 void topo()
     9 {
    10     int k=0,i,j;
    11     for(j = 0 ; j < n ; j++)
    12     {
    13         for(i = 1 ; i <= n ; i++)
    14         {
    15             if(num[i] == 0)
    16             {
    17                 m=i;
    18                 break;
    19             }
    20         }
    21         que[k++]=m;
    22         num[m]=-1;
    23         for(i = head[m] ; i != -1 ; i=st[i].next)
    24         {
    25             num[st[i].to]--;
    26         }
    27     }
    28     for(i = 0 ; i < k ; i++)
    29     {
    30         printf("%d",que[i]);
    31         if(i == k - 1)
    32             printf("\n");
    33         else
    34             printf(" ");
    35     }
    36 }
    37 int main()
    38 {
    39     while(scanf("%d %d",&n,&m)!=EOF)
    40     {
    41         memset(num,0,sizeof(num));
    42         memset(head,-1,sizeof(head));
    43         for(i = 0 ; i < m ; i++)
    44         {
    45             scanf("%d %d",&a,&b);
    46             st[i].to=b;
    47             st[i].next=head[a];
    48             head[a]=i;
    49             num[b]++;
    50         }
    51         topo();
    52     }
    53 }

队列查询

1 #include<cstdio>
     2 #include<queue>
     3 #include<string.h>
     4 #include<functional>
     5 using namespace std;
     6 int n,m,i,j,a,b,num[505],key,map[505][505];
     7 void topo()
     8 {
     9     priority_queue<int,vector<int>,greater<int> >que;
    10     int i,j,m;
    11     for(i = 1 ; i <= n ; i++)
    12     {
    13         if(num[i] == 0)
    14         {
    15             que.push(i);
    16             num[i]=-1;
    17         }
    18     }
    19     key=1;
    20     while(!que.empty())
    21     {
    22         m=que.top();
    23         que.pop();
    24         if(key)
    25         {
    26             printf("%d",m);
    27             key=0;
    28         }
    29         else
    30         {
    31             printf(" %d",m);
    32         }
    33         for(i = 1 ; i <= n ; i++)
    34         {
    35             if(map[m][i])
    36             {
    37                 num[i]--;
    38                 if(num[i] == 0)
    39                 {
    40                     que.push(i);
    41                 }
    42             }
    43         }
    44     }
    45     printf("\n");
    46 }
    47 int main()
    48 {
    49     while(scanf("%d %d",&n,&m)!=EOF)
    50     {
    51         memset(num,0,sizeof(num));
    52         memset(map,0,sizeof(map));
    53         for(i = 0 ; i < m ; i++)
    54         {
    55             scanf("%d %d",&a,&b);
    56             if(map[a][b] == 0)
    57             {
    58                 map[a][b]=1;
    59                 num[b]++;
    60             }
    61         }
    62         topo();
    63     }
    64 }

转载于:https://www.cnblogs.com/yexiaozi/p/5740733.html

[Link 1]: http://www.cnblogs.com/yexiaozi/p/5740649.html