确定比赛名次——拓扑排序

传送门HDU1285

描述

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

输入

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

输出

给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。

样例

  • Input
    4 3
    1 2
    2 3
    4 3
  • Output
    1 2 4 3

思路

  • 在一个有向无环图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。
  • 先统计所有节点的入度,对于入度为0的节点就可以分离出来,然后把这个节点指向的节点的入度减一。
  • 一直做改操作,直到所有的节点都被分离出来。
  • 如果最后不存在入度为0的节点,那就说明有环,不存在拓扑排序,也就是很多题目的无解的情况。
  • 按字典序输出的时候用优先队列处理即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
#define INIT(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e4+7;
const int mod=1e9+7;
struct Edge{
int to,next;
}edge[maxn];
priority_queue< int,vector<int>,greater< int> >cnt;
int Begin[maxn],tot=0,in[maxn];
void add(int x,int y){
edge[tot]=(Edge){y,Begin[x]};
Begin[x]=tot++;
}
void topo(int n){
for(int i=1;i<=n;i++){
if(in[i]==0)
cnt.push(i);
}
vector<int>ans;
while(!cnt.empty()){
int now=cnt.top();cnt.pop();
ans.push_back(now);
for(int i=Begin[now];~i;i=edge[i].next){
in[edge[i].to]--;
if(in[edge[i].to]==0)
cnt.push(edge[i].to);
}
}
for(int i=0;i<ans.size();i++)
printf("%d%c",ans[i]," \n"[i==ans.size()-1]);
}
int main(){
int n,m,x,y;
while(~scanf("%d%d",&n,&m)){
INIT(Begin,-1);
INIT(in,0);
tot=0;
while(m--){
scanf("%d%d",&x,&y);
in[y]++;
add(x,y);
}
topo(n);
}
return 0;
}
Donate comment here