考研408 2019年41题

题目：

假设有 $n$ 个点和 $m$ 条边构成的无向图，其中每条边权值为 $1$ 或 $2$。请设计一个时间复杂度为 $O(m+n)$ 的算法，判断该图是否为二分图。

二分图：若将图的所有节点分为两个不相交的集合 $U$ 和 $V$，并且图中的每条边所连接的两个节点一个属于集合 $U$，另一个属于集合 $V$，则称该图为二分图。

输入格式：

第一行包含一个整数 T，表示测试数据组数。

每组测试数据包含若干行，格式如下：

第一行包含两个整数 n 和 m，表示该图的节点数和边数。

接下来 m 行，每行包含两个整数 x 和 y，表示该图中存在一条连接节点 x 和节点 y 的边。

输出格式：

每组数据输出一个结果，每个结果占一行。

如果该图为二分图，输出 Yes。

否则输出 No。

数据范围：

1≤T≤10

1≤n≤10^5

1≤m≤10^5

样例

输入样例：
2
5 5
1 2
2 3
3 4
4 5
1 5
4 4
1 2
2 3
3 4
4 1
输出样例：
No
Yes

题解：

一个图为二分图，当且仅当这个图的任意一个环边的权值都为偶数。

这个结论可以通过染色法进行证明，也可以通过匈牙利算法进行证明。

这里介绍一种使用染色法的证明方法。

首先需要理解什么是染色法。

染色法是一种图论算法，用于判断一个无向图是否为二分图。

具体来说，就是给图中的每个节点染上黑色或白色，使得相邻节点颜色不同，如果可以完成染色，则该图为二分图。

下面是染色法的流程：

1.任选图中一个节点，将其染成黑色。

2.将与该节点相邻的节点染成白色。

3.将与白色节点相邻的黑色节点染成白色，与黑色节点相邻的白色节点染成黑色。

4.重复以上步骤，直到所有节点都被染色。

如果出现某个节点无法染色的情况，说明该图不是二分图。

证明：

首先假设存在一个环边的权值都为偶数的图不是二分图，即存在某个节点无法染色。

考虑环边的权值都为偶数的性质，即假设存在一个长度为 $n$ 的环，环上的边权值分别为 $a_1,a_2,...,a_n$，则有：

$$\sum_{i=1}^{n} a_i\bmod 2=0$$

其中 $\bmod$ 表示取余数。

假设节点 $A$ 无法染色，说明节点 $A$ 和其相邻的节点 $B$ 颜色相同。

设节点 $B$ 染成了黑色，即节点 $A$ 和节点 $B$ 之间的边权值为 $1$。

那么节点 $A$ 和其相邻的节点 $C$ 也颜色相同。设节点 $C$ 染成了黑色，即节点 $A$ 和节点 $C$ 之间的边权值为 $1$。

那么节点 $B$ 和 $C$ 之间的边权值为 $2$，即 $a_{BC}=2$。

继续考虑节点 $B$ 和其相邻的节点 $D$，由于节点 $B$ 和节点 $C$ 颜色相同，所以节点 $B$ 和节点 $D$ 颜色不同，设节点 $D$ 染成了黑色，即节点 $B$ 和节点 $D$ 之间的边权值为 $1$。

那么节点 $A$ 和 $D$ 之间的边权值为 $2$，即 $a_{AD}=2$。

继续考虑节点 $C$ 和其相邻的节点 $E$，由于节点 $C$ 和节点 $D$ 颜色相同，所以节点 $C$ 和节点 $E$ 颜色不同，设节点 $E$ 染成了黑色，即节点 $C$ 和节点 $E$ 之间的边权值为 $1$。

那么节点 $B$ 和 $E$ 之间的边权值为 $2$，即 $a_{BE}=2$。

最后考虑节点 $D$ 和其相邻的节点 $A$，由于节点 $D$ 和节点 $E$ 颜色相同，所以节点 $D$ 和节点 $A$ 颜色不同，设节点 $A$ 染成了黑色，即节点 $D$ 和节点 $A$ 之间的边权值为 $1$。

那么节点 $E$ 和 $A$ 之间的边权值为 $2$，即 $a_{EA}=2$。

此时，我们得到了一个环，其边权值分别为 $a_{AD},a_{DE},a_{EB},a_{BA}$ 和 $a_{AE}$，并且：

$$\sum_{i=1}^{5}a_i\bmod 2=0$$

其中 $\bmod$ 表示取余数。

这与假设矛盾，因此得证。

Code：