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啊