对于一个图\(G=（V,E）\)，若能将其点集分为两个互不相交的两个子集\(X、Y\)，
使得\(X∩Y=\phi\)，且对于\(G\)的边集\(V\)，若其所有边的顶点全部一侧属于\(X\)，
一侧属于\(Y\)，则称图\(G\)为一个二分图。
当且仅当无向图\(G\)的回路个数为偶数时，图\(G\)为一个二分图。
无回路的图也是二分图。
在二分图\(G\)中，任选一个点\(V\)，
使用\(BFS\)预处理出其他点相对于\(V\)的距离（边权为\(1\)）
对于每一条边\(E\)，枚举它的两个端点，若其两个端点的值，
一个为奇数，一个为偶数，则图\(G\)为一个二分图。
对于一个二分图\(G\)的子图\(M\)（前提是在二分图中）,若\(M\)的边集\(E\)的的任意两条边都不连接同一个顶点，
则称\(M\)为\(G\)的一个匹配。特别的，其中边数最多的\(M\)称为二分图的最大匹配。
建立有向图\(G\)，分为二分图的左侧和右侧。
优先选择左侧序号更小的连接可能的边。
对于两个点的目标点“冲突”的时候，采取“协商”的办法。
即序号小的连接可能连接的另一条边。
若“协商”失败，则放弃序号较大的点的边。
推荐看这篇大佬的博客https://www.luogu.org/blog/fusu2333/post-2018-wu-yi-qing-bei-pei-xun-er-fen-tu-xiong-ya-li-suan-fa-post，以上内容基本来自这里
原文：https://www.cnblogs.com/Liuz8848/p/10919737.html