二分图

二分图的结论和算法 防止忘记

• 匈牙利算法的过程是，枚举每一个左部点 $u$ ，然后枚举该左部点连出的边，对于一个出点 $v$，如果它没有被先前的左部点匹配，那么直接将 $u$ 匹配 $v$，否则尝试让 $v$ 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 $u$ 匹配 $v$，否则 $u$ 失配。

• 二分图最大独立集等于总点数减去最大匹配