救命调了几个小时了!!!!急救
  • 板块P1347 排序
  • 楼主A_r_k
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/9/9 00:09
  • 上次更新2024/9/9 16:52:49
查看原帖
救命调了几个小时了!!!!急救
1254229
A_r_k楼主2024/9/9 00:09
from collections import deque, defaultdict
def toposort(g,rd,n):
    path = []
    queue = deque([])
    cnt = 0
    flag = False
    for node in g:
        if rd[node] == 0:queue.append(node)
    while queue:
        cur = queue.popleft()
        path.append(cur)
        cnt += 1
        for child in g[cur]:
            rd[child] -= 1
            if rd[child] == 0:queue.append(child)
    for i in rd:
        if rd[i] > 0:
            flag = True
            break
    return [path,flag]
def solve():
    n, m = map(int, input().split())
    g = defaultdict(lambda: [])
    rdfa = defaultdict(lambda: 0)
    # 如果拓扑序的长度>=n,则直接返回前n个
    # 如果无法确定关系,则优先输出有矛盾的
    for i in range(m):
        u, v = input().split('<')
        g[u].append(v)
        rdfa[v] += 1
        rd = rdfa.copy()
        topo,ishuan = toposort(g,rd,n)
        # 有环肯定不行
        if ishuan :
            return f'Inconsistency found after {i + 1} relations.'
        if len(topo) >= n:
            ans = ''.join([str(x) for x in topo])
            return f'Sorted sequence determined after {i + 1} relations: {ans}.'
    return 'Sorted sequence cannot be determined.'
print(solve())

关于下面这个样例

4 6
C<D
C<B
B<A
C<D
D<A
A<A

为什么结果不是

Sorted sequence determined after 3 relations: CDBA.

明明前三个就可以确定拓扑序了啊,求大佬救命啊QAQ 还有关于 测试点三,本地输出

Sorted sequence cannot be determined.

跟线上的预期输出一样为什么还是WA啊

2024/9/9 00:09
加载中...