一般图最大匹配

在二分图中，通常使用匈牙利算法来解决最大匹配的问题，但在一般图中，由于存在奇环，使得该算法无法找到最大匹配。

如下图所示

橙色为已匹配的边，黑色为未匹配的边。

如果我们dfs时走$1\to 3\to 5\to 4\to 2$，此时增广失败，的$2,3,4,5$都被打上了标记。但本图中确实存在一条可行的增广路$1\to 2\to 4\to 5\to 3\to 6$

---

考虑到如果一个$n$元环中，可以得到$\lfloor\frac{n}{2}\rfloor$个匹配，那么对于奇环，该环中仅有一个点不能在环内匹配。

因而我们可以将环缩成一个点$v$，缩点后对于经过$v$的增广路，都可以在原图中找到对应的增广路。

参考

https://rqy.moe/Algorithms/flower-tree/

https://blog.bill.moe/blossom-algorithm-notes/