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
|
L = {
(s := l.strip().split(": ")) and s[0]: [-1, -1, False, set(s[1].split(" "))]
for l in open("input").readlines()
}
# bidirectionality
for l in list(L.keys()):
for k in L[l][3]:
if k not in L:
L[k] = [-1, -1, False, set()]
L[k][3].add(l)
import networkx as nx # :)
cut = nx.minimum_edge_cut(
nx.from_dict_of_lists({i: n[3] for (i, n) in L.items()})
)
for s, d in cut:
L[s][3].remove(d)
L[d][3].remove(s)
i = 0
s = []
res = 1
# probably overkill lol
def scc(n):
# globalism ftw
global i
global s
global res
L[n] = [i, i, True, L[n][3]]
i += 1
s.append(n)
for e in L[n][3]:
if L[e][0] == -1:
scc(e)
L[n][1] = min(L[n][1], L[e][1])
elif L[e][2]:
L[n][1] = min(L[n][1], L[e][0])
if L[n][1] == L[n][0]:
comp = set()
while True:
e = s.pop()
L[e][2] = False
comp.add(e)
if n == e:
break
res *= len(comp)
for n in L.keys():
if L[n][0] == -1:
scc(n)
print(res)
|
