描述
有N个比赛队(1<=N<=500),编号依次为1,2,3,。。。。,N进行比赛,比赛结束后,裁判委员会要将所有参赛队伍从前往后依次排
名,但现在裁判委员会不能直接获得每个队的比赛成绩,只知道每场比赛的结果,即P1赢P2,用P1,P2表示,排名时P1在P2之前。现在请你编程序确定
排名。
输入
输入有若干组,每组中的第一行为二个数N(1<=N<=500),M(0<=M<=10000);其中N表示队伍的个数,M表示接着有M行的输入数据。接下来的M行数据中,每行也有两个整数P1,P2表示即P1队赢了P2队。
输出
给出一个符合要求的排名。输出时队伍号之间有空格,最后一名后面没有空格。
其他说明:符合条件的排名可能不是唯一的,此时要求输出时编号小的队伍在前;输入数据保证是正确的,即输入数据确保一定能有一个符合要求的排名。
样例输入
4 3
1 2
2 3
4 3
样例输出
1 2 4 3
拓扑排序,因为要按照字典序输出每个结点,所以开了个优先队列。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77 |
#include <stdio.h> #include <string.h> #include <queue> #include <iostream> using
namespace
std; #define MAXN 505 int
n,m,cnt; int
head[MAXN]; int
indgree[MAXN]; int
flag[MAXN]; struct
EdgeNode{ int
to; int
next; }edge[MAXN*20]; struct
INT { int
nod; friend
bool
operator <( INT
a, INT
b){ return
a.nod > b.nod; } }; void
addedge( int
u, int
v){ edge[cnt].to=v; edge[cnt].next=head[u]; indgree[v]++; head[u]=cnt++; } void
topsort(){ priority_queue< INT > Q; int
iq=0; for ( int
i=1; i<=n; i++){ if (indgree[i]==0){ INT
t; t.nod=i; Q.push(t); } } while (!Q.empty()){ INT
now=Q.top(); Q.pop(); flag[iq++]=now.nod; for ( int
k=head[now.nod]; k!=-1; k=edge[k].next){ indgree[edge[k].to]--; if (indgree[edge[k].to]==0){ INT
t; t.nod=edge[k].to; Q.push(t); } } } if (iq==n){ for ( int
i=0; i<n; i++){ if (!i) printf ( "%d" ,flag[i]); else printf ( " %d" ,flag[i]); } printf ( "\n" ); } } int
main( int
argc, char
*argv[]) { int
u,v; while ( scanf ( "%d %d"
,&n ,&m)!=EOF){ cnt=0; memset (head,-1, sizeof (head)); memset (indgree,0, sizeof (indgree)); for ( int
i=1; i<=m; i++){ scanf ( "%d%d" ,&u,&v); addedge(u,v); } topsort(); } return
0; } |
原文:http://www.cnblogs.com/chenjianxiang/p/3535482.html