当前位置:首页 > 图论 > 拓扑排序 > 正文
洛谷P1960郁闷的记者[NOI导刊]
111+

题目大意:已知n支足球队m次比赛的结果(没有平局),你能确定他们的排名吗?只要a赢过b,那么a就比b排名靠前!

题目描述

你是一个体育报社的记者,你接受到一个艰难的任务:有N支足球队参加足球比赛,现在给你一些比赛的结果,需要你给出各支球队的排名,从1到N。

以下是给你的一些信息:

(1)没有平局;

(2)不同的球队排名不能相同;

(3)对于所有满足l≤a<b≤n,第a名的球队一定可以打败第b名的球队。

给你部分比赛结果,要求给出排名,并且判断是否存在另一种排名方法满足给你的比赛结果。

输入输出格式

输入格式

第一行输入N(1≤N≤5000),表示球队的数量,编号为l到N。第二行输入M(1≤M≤100,000),表示给出的比赛场数。接下来M行,每行两个整数X\_i,Y\_i,表示X\_i能打败Y\_i。

输出格式

输出包含N+1行,前N行描述球队的排名,第i个数表示第i名的球队,第N+1行包含一个整数,如果为0表示不存在其他的排名方法,如果为1表示还有其他的排名方法。

输入输出样例

输入样例 #1

3
2
2  1
2  3

输出样例 #1

2
1
3
1

说明

【数据范围】

30%的数据满足:l≤N≤7,1≤M≤15

60%的数据满足:l≤N≤100,1≤M≤2000

100%的数据满足:l≤N≤5000,1≤M≤100000

本题已加入spj,如果输出的最后一行错误将会提示”Your decide is wrong!”

如果存在多种排名情况,排名错误将会提示”Wrong ranks!”

如果情况固定且您的答案错误将会提示”In line X,Your ans is wrong:expected = X,found = Y”

解题思路

赢的先输出,输的后输出,显示是拓扑排序。当队列中元素超过1个的时候,就会 有多个拓扑序,排名不唯一。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

洛谷P1960郁闷的记者[NOI导刊]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter