我自己想了一个证法，就是如果有x，y和z三个点，扩展域后变成xA，xB，yA，yB，zA，zB六个点：
假设x和y连一条边会导致zA和zB相连，且xA和yA不在一组，不妨设xA和zA在一组，yB和zB在一组，这时候可知xB和zB也在一组，yA和zA也在一组，这样xA和yA就一定在一组，假设不成立，说明不会出现这样的情况，xA和yA在一组可以处理所有不是二分图的情况。
但是感觉这个证法不够优美不够本质，请问各位大佬有没有更好的方法证明？
by 滑稽的小宫 @ 2021-07-11 20:26:09
好问题。虽然时间比较久了，但还是说一下我的理解吧：
考虑这样的一张图：
左侧有1至n个点，颜色为白（对应1至n号点）；右侧也有1至n个点，颜色为黑（对应n+1至2n号点）。某一行表示原图上的某一个点，黑白的颜色区分了它在二分图上的阵营。显然若始终没有冲突发生，则同一行的黑白两点就不会同时被选中。这样，待到所有操作结束后，每一行有且只有一个颜色，也就是说原图上的点有且只有一个阵营。阵营数就是2，所以原图就是二分图。
不晓得说得好不好，还望多多包涵。
by Yahbim @ 2021-08-02 19:58:00
@[滑稽的小宫](/user/65743)
by Yahbim @ 2021-08-04 17:40:37
@[Yahbim](/user/372708)
但是代码没有检查每一对点是否在一个集合内吧？如果我当前一对点不在一个集合内，但是连上这条边以后说不定就会在集合内了？
就是说修改的时候只检查被修改的两对节点为什么就可以判断？其他节点的无解情况为什么不用判断？
by 滑稽的小宫 @ 2021-08-05 21:41:48
@[滑稽的小宫](/user/65743)
您的考虑是这样的么：
存在集合 $S,T$ ，使得 $A\in S,B\in T$ ，其中 $A$ 和 $B$ 在同一行。当通过任意的边 $E=\{U,V\}$ 连接起 $S$ 和 $T$ 时，$A$ 和 $B$ 会产生无解情况，而 $U$ 和 $V$ 则不一定，所以就可能检查不出来无解？
这种情况是不存在的。简要的说，是因为对称性，如果两个集合包括了同一行的两个点，那么它们就是对称的。
每次连接都是对称地连接了两组点，所以对于集合 $S$ 和点 $A$ ， 必然存在集合 $S^{\prime}$ ，使得 $B\in S^{\prime}$ 。因为 $B$ 仅在一个集合内出现，所以 $S^{\prime}=T$ 。这样，$S$ 和 $T$ 就是对称的。所以这两个集合要不相安无事，要不全都有事，随便检查一对点都行。
by Yahbim @ 2021-08-06 18:26:34
@[Yahbim](/user/372708)
明白了，谢谢大佬！
by 滑稽的小宫 @ 2021-08-06 21:15:33