-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy patht35.py
72 lines (61 loc) · 1.77 KB
/
t35.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
63
64
65
66
67
68
69
70
71
import sys
n = int(input())
arr = [[] * n for _ in range(n)]
graph = {x:set() for x in range(1,n+1)}
for i,line in enumerate(sys.stdin.readlines(), start=1):
vals = line.split()
assert len(vals) == n, f"err: line #{i}"
for j,val in enumerate(vals, start=1):
if val == '1':
graph[i].add(j)
def solve(graph):
""" find any cycle """
if not graph:
return None
visited = [None] * (max(graph.keys()) + 1) # None, 1, 2
ret = []
for k in graph:
if visited[k] is not None:
continue
# start for k
stack = [k]
while stack:
# print(stack, file=sys.stderr)
s = stack.pop()
if visited[s] is None:
visited[s] = 1
for c in graph[s]:
vc = visited[c]
if vc is None:
# go deeper
visited[c] = 1
stack.append(s)
stack.append(c)
break
elif vc == 1:
if not stack or stack[-1] == c: # child is the parent at the same time
pass
else:
# Cycle found
ret = stack[stack.index(c):] + [s]
stack = []
break
elif vc == 2:
pass
else:
raise ValueError(f"impossible {vc=}")
else:
# Done with s
visited[s] = 2
if ret:
return ret
else:
continue # next k
# print(graph, file=sys.stderr)
ans = solve(graph)
if ans is None:
print('NO')
else:
print('YES')
print(len(ans))
print(*reversed(ans))