-
Notifications
You must be signed in to change notification settings - Fork 6
/
bilateral.py
58 lines (51 loc) · 1.89 KB
/
bilateral.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
import sys; input()
from random import choice
t, r, n = [], {}, []
for l in sys.stdin:
a, b = map(int, l.split())
t.append((a, b))
if a not in r: r[a] = len(r); n.append(a)
if b not in r: r[b] = len(r); n.append(b)
def aug(l):
if vis[l]: return 0
vis[l] = 1
for r in g[l]:
if match[r] == -1 or aug(match[r]): match[r] = l; return 1
q, vc = [], []
for exc in range(2):
# MCBM - Konig's theorem to find MVC
V = len(r)
g = [[] for _ in range(V)]
match = [-1]*V
free = {*(i for i in range(V) if n[i] < 2000)}
for a, b in t:
if exc and (a == 1009 or b == 1009): continue
a2, b2 = r[a], r[b]; g[a2].append(b2)
for l in range(V):
if (can:=[r for r in g[l] if match[r] == -1]): free.discard(l); match[choice(can)] = l
for f in free: vis = [0]*V; aug(f)
# matching graph
mg = [set() for _ in range(V)]
for a in range(V):
for b in g[a]:
if match[b] != -1: mg[match[b]].add(b)
# make the graph undirected for DFS prep
for a, b in t:
if exc and (a == 1009 or b == 1009): continue
a2, b2 = r[a], r[b]; g[b2].append(a2)
vis = [0]*V
z = set() # all verts connected to unmatched free verts
for i in range(V):
if n[i] < 2000 and not mg[i]: # DFS on unmatched free verts for alternating path
q.append(2*i)
while q:
umt = q.pop()
u, mt = umt//2, umt%2
if vis[u]: continue
z.add(u); vis[u] = 1
for w in g[u]:
if (u in mg[w] or w in mg[u])^(1-mt): q.append(2*w+1-mt)
vc.append([n[i] for i in range(V) if (n[i] < 2000)^(i in z)]) # mvc = (L-Z)|(R&Z)
x, y = vc
if len(y) < len(x): print(len(y)+1, 1009, *y) # 1009 not in y so adding it should make it the optimal solution
else: print(len(x), *x)