二分图最大匹配数量，匈牙利算法求解 python，本质上是找增广回路
"""
# File : hungary.py
# Time ：2022/8/28 21:08
# Author ：notomato
# Description：
#
"""
'''
'''
# 六个点
# 第i个坐标存他相邻的点
from collections import defaultdict
n = 8
arr = [1,2,2,3,3,5,1]
vis = [0 for _ in range(n+1)]
g = defaultdict(list)
conn = defaultdict(bool)
for i, v in enumerate(arr):
g[i+2].append(v)
g[v].append(i+2)
conn[(v, i + 2)] = True
conn[(i+2, v)] = True
# 二分图
two = [set(), set()]
q = [1]
vis[1] = True
level = 0
# 分为两部分，按照树的层来分的
while len(q) > 0:
tmp = []
for nxt in q:
two[level&1].add(nxt)
for nnxt in g[nxt]:
if not vis[nnxt]:
vis[nnxt] = True
tmp.append(nnxt)
q = tmp
level += 1
print(two)
a,b = list(two[0]), list(two[1])
def match(x):
for y in b:
if conn[(x,y)] and not vised[y]:
vised[y] = 1
if connb[y] == 0 or match(connb[y]) != 0:
connb[y] = x
return 1
return 0
ans = 0
connb = defaultdict(int)
for x in a:
vised = defaultdict(int)
if match(x):
ans += 1
print(ans)
print(connb)