-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patht34.py
62 lines (53 loc) · 1.58 KB
/
t34.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
import sys
nvert, nedg = map(int, input().split())
graph = {x:[] for x in range(1, nvert+1)}
for line in sys.stdin.readlines():
line = line.strip()
if not line: # skip empty line
continue
a,b = line.split()
a = int(a); b = int(b)
graph.setdefault(a, []).append(b)
graph.setdefault(b, [])
def solve(graph):
""" Topological sorting + loop detection. """
if not graph:
return []
visited = [None] * (max(graph.keys()) + 1) # None, 1, 2
ret = []
for k in graph:
if visited[k] is not None:
continue
stack = [k]
while stack:
s = stack.pop()
if visited[s] is None:
visited[s] = 1
for child in graph[s]:
vc = visited[child]
if vc is None:
stack.append(s)
stack.append(child)
visited[child] = 1
break
elif vc == 1: # already in path
# if s == child: # loop
# pass
# else:
# # Cycle found
return None
elif vc == 2:
pass
else:
raise ValueError(f"{vc=}")
else:
# finished or no children
ret.append(s)
visited[s] = 2
# print(f"{stack=}", file=sys.stderr)
return ret
# print(f"{graph=}", file=sys.stderr)
ans = solve(graph)
if ans is None:
ans = [-1]
print(*reversed(ans))