洛谷P1960郁闷的记者[NOI导刊]
1343+
作者：crxis 发布：2021-06-22 分类：拓扑排序
题目大意：已知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个的时候，就会 有多个拓扑序，排名不唯一。
程序实现
