摘要：
如果图中没有奇环，则该图必须是二部图。如果没有找到，那么根据着色原理，每条边两端的着色必须不同。然后根据二分图的定义，我们可以知道该图是二分图。模板问题链接：染色法确定的二分图的代码如下：#include＜iostream＞#incluse＜algorithm＞#inclaude＜cstring＞#in包括＜cstdio＞usingnamespacestd；常数N=100010，M=200010；structEdge｛intto，next；｝边缘[M]；积分；整数，m；inth[N]，颜色[N]；voidadd_edge｛edge[++cnt].to=v；edge[cnt].next=h[u]；h[u]=cnt；｝booldfs｛color[u]=c；对于｛intto=edge[i].to；如果｛returnfalse；｝艾尔塞夫（！
首先明确概念：
二分图：设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
奇数环：一个图中边数为奇数的环。
染色法原理：
首先任意取出一个顶点进行染色，和该节点相邻的点有三种情况:
1.如果未染色，那么继续染色此节点（染为另一种颜色）
2.如果已染色但和当前节点颜色不同，则跳过该点
3.如果已染色并且和当前节点颜色相同，返回失败(该图不是二分图)
明确二分图、奇数环、染色法之间的关系：
如果一个图中存在奇数环，那么这个图一定不是二分图；这一点显然成立。
如果一个图中不存在奇数环，那么这个图一定是二分图：
证明：用染色法。从某个点开始逐层交叉染色，在染色过程中：
若发现有某条边的两个端点着色相同，则必定存在奇数环①，与题意相矛盾。
若没有发现，则根据染色法原理，每一条边的两端着色必然不同，那么根据二分图的定义，就可知这个图是一个二分图。
①的证明：
不妨设这条边的两个端点着色都为1，且这两点必然是由同一个源点扩展而来。那么根据染色法原理，因为这两个点的着色相同，那么从源点到这两个点所经过的边数（假设分别为x和y）的奇偶性必然相同，那么这个环的总边数为x+y+1，由数学知识得这个数必然是奇数。
证毕！
模板题链接：染色法判定二分图
代码如下：
#include <iostream>#include <algorithm>#include <cstring>#include <cstdio> using namespacestd; const int N = 100010, M = 200010; structEdge{ intto,next; }edge[M];intcnt; intn,m; inth[N],color[N]; void add_edge(int u,intv) { edge[++cnt].to=v; edge[cnt].next=h[u]; h[u]=cnt; } bool dfs(int u,intc) { color[u]=c; for(int i=h[u]; ~ i;i=edge[i].next) { int to=edge[i].to; if(color[to]==c) { return false; } else if(!color[to]&&!dfs(to,3-c))return false; } return true; } intmain() { scanf("%d%d",&n,&m); memset(h,-1,sizeofh); for(int i=1;i<=m;i++) { int a,b;scanf("%d%d",&a,&b); add_edge(a,b);add_edge(b,a); } bool flag=true; for(int i=1;i<=n;i++) { if(!color[i]) { if(!dfs(i,1)) { flag=false; break; } } } if(flag)printf("Yes "); else printf("No "); }