若无向图 G=(V,E) 的顶点集 V 可以分割为两个互不相交的子集，且图中每条边的两个顶点分别属于不同的子集，则称图 G 为一个二分图。
我们使用图搜索算法从各个连通域的任一顶点开始遍历整个连通域，遍历的过程中用两种不同的颜色对顶点进行染色，相邻顶点染成相反的颜色。这个过程中倘若发现相邻的顶点被染成了相同的颜色，说明它不是二分图；反之，如果所有的连通域都染色成功，说明它是二分图。
我们知道如果是二分图的话，那么图中每个顶点的「所有邻接点」属于同一集合，且「不与顶点」处于同一集合。因此我们可以使用并查集来解决这个问题，我们遍历图中每个顶点，将当前顶点的所有邻接点进行合并，并判断这些邻接点中是否存在某一邻接点已经和当前顶点处于同一个集合中了，若是，则说明不是二分图。
上述三种方法，时间复杂度是 O(N + M), 空间复杂度是 O(N)，其中 N 是无向图的顶点数，M 是无向图的边数。
实现的代码参考例题：785-[二分图]-判断二分图
在二分图上，最常见的问题是求 二分图最大匹配/最大独立集。二分图的最大匹配，简单来说就是找到尽可能多的两两匹配的关系。比如说在某场相亲现场，主持人先让所有男生女生都写好自己感兴趣的若干个异性，主持人需要尽可能多的凑一对对男女去约会。
这个问题经典的解法是 匈牙利算法，这块知识超过了面试要求，感兴趣的同学可以自行查阅资料。
说到相亲，还有一个著名的算法叫做 稳定婚姻问题。就是说，主持人的你安排男男女女相亲，如果当前是男 1 和女 2 在一起，男 2 和女 1 在一起，男1更喜欢女1，女1也更喜欢男1，那么他俩就会私奔，你的安排相亲就是 不稳定 的。对于一群男生和女生，你需要给出一个 稳定 的相亲方案。这个有趣的算法，感兴趣的同学可以看下 matrix67 大神对于这个故事的阐述～ 什么是算法：如何寻找稳定的婚姻搭配
力扣 886.可能的二分法
题目描述： 给定 N 人（编号为 1, 2, ..., N），将其分为两组。每个人都可能有不喜欢的人，那么他们不应该属于同一组，当可以用这种方法将这些人分为两组时，返回 true；否则返回 false。
题目分析： 这题实质也是判断是否构成二分图（以每个人为顶点，以“不喜欢”为边，即若 A 不喜欢 B，则在 A 与 B 之间建边）。
力扣 1349. 参加考试的最大学生数
题目描述： 给定一个教室里 n * m 的座位，里面有一些座位是坏的不能坐。你需要安排学生的座位，要求每个学生的左上/右上/左/右都没有其它学生。要求尽可能多的安排学生考试，问最多可以安排几个学生。
提示： 这道题涉及到求 二分图最大独立集，也可以用带状态压缩的动态规划来做。