首页 > 试题广场 >

比赛名次

[编程题]比赛名次

热度指数：3096 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有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队。

输出描述:

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

示例1

输入

输出

1 2 4 3

算法知识视频讲解

Python

ElonB

""""
每次找到在第一列且不在第二列，或没有比赛结果的队伍，
输出最小编号，删除包含此最小编号队伍的比赛结果，重复上一步骤。
优化时间复杂度，优化比赛结果的存储格式，设置各队伍的入度(输的数量),可以用优先级队列进一步优化
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open("input.txt", "r")
    try:
        while True:
            n, m = map(int, input().strip().split())
            edge = [[] for _ in range(n + 1)]
            indegree = [0] * (n + 1)
            for _ in range(m):
                a, b = map(int, input().strip().split())
                edge[a].append(b)
                indegree[b] += 1
            pre = []
            ans = []
            for i in range(1, n + 1):
                if indegree[i] == 0:
                    pre.append(i)
            while pre:
                ans.append(min(pre))
                pre.remove(ans[-1])
                for k in edge[ans[-1]]:
                    indegree[k] -= 1
                    if indegree[k] == 0:
                        pre.append(k)
            print(' '.join(map(str, ans)))
    except:
        pass

编辑于 2019-07-14 09:52:25 回复(0)