AcWing算法分享系列——二分图

这是AcWing算法分享系列的第一篇文章，我们先从图论的知识下手（因为我觉得图论的只是好理解些）。
这次我们主要讲的就是二分图，二分图这次我们主要讲的就是最基础的两个板块：

• 二分图的判定（染色法）
• 二分图的完美匹配（匈牙利算法）

我们这一篇文章先从二分图的概念开始入手吧。

二分图（偶图）

概念

概念：在一个图中，如果能够把全部点分到两个集合中，且每一个集合都没有边与同一个集合中的点联通，这样的图就是二分图（也叫偶图）。
tips：二分图这个性质通常用于无向图，但是有些有向图也有二分图的性质。
不懂，下面这张图就是一个二分图：

我们可以发现，两个集合中就没有边的相连，所以，这张图就是一个二分图。

性质

• 二分图中不可能含有奇数环，因为每一次的一个点需要走偶数次才能走回自己所在的集合，所以二叉树中不能有奇数环
• 不含有奇数环的一定是二分图，这个引理是可以证明的