首页 > 代码库 > HDU 1285 拓扑排序

HDU 1285 拓扑排序

2024-07-14 07:42:08   222人阅读

确定比赛名次

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 11543    Accepted Submission(s): 4603


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
 
 
 
WA了一次  ，原因是可能有重复的，比如输入两两次5 3
 
附个数据：
6 115 35 35 15 45 23 13 26 46 24 24 2结果是：5 3 1 6 4 2

代码：
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <stack> 6 #include <queue> 7 #include <map> 8 #include <vector> 9 #include <sstream>10 #include <string>11 using namespace std;12 13 struct mem{14     int x, y;15 }a[505];16 17 bool cmp(mem a,mem b){18     if(a.x==b.x) return a.y<b.y;19     return a.x<b.x;20 }21 22 main()23 {24     int du[505];25     int ma[505][505];26     vector<int>ve[505];27     int n, m, i, j, k;28     while(scanf("%d %d",&n,&m)==2){29         memset(du,0,sizeof(du));30         memset(ma,0,sizeof(ma));31         for(i=0;i<=n;i++) ve[i].clear();32         for(i=0;i<m;i++) {33             scanf("%d %d",&a[i].x,&a[i].y);34             if(!ma[a[i].x][a[i].y])35             {36                 du[a[i].y]++;37                 ve[a[i].x].push_back(a[i].y);38             }39             40             ma[a[i].x][a[i].y]=1;41         }42     //    sort(a,a+m,cmp);43 /*    44     for(i=1;i<=n;i++){45         printf("%d ",du[i]);46     }47     cout<<endl<<endl;*/48         int b[505], f=0, l=0;49         for(k=1;k<=n;k++){50             f=0;51             for(i=1;i<=n;i++){52             if(du[i]==0) {53                 for(j=0;j<ve[i].size();j++){54                     du[ve[i][j]]--;55                 }56                 b[l++]=i;57                 du[i]=-1;58                 f++;59                  break;60              }61             62            }63            if(!f) break;64         }65         printf("%d",b[0]);66         for(i=1;i<l;i++) printf(" %d",b[i]);67         cout<<endl;68         69     }70 }

 

 

 


联系
我们