所谓二分图，即可以把途中所有的点分成两类，满足关系是在同一类的点之间一定没有相连的边，不在同一类的点之间可以有相连的边。注意是可能有，不是一定都要有，且只能有两类不能有多类。

染色法基于一个定理，即奇数点构成的环一定不是二分图，证明：假如是同一类的两个同类的点相连，则在环除了这两个点以外的点，应该都满足交叉的，则必定会有奇数个，再加上这两个点，一共是奇数个点，因此一定不是二分图。

染色法具体的思路：

对于每个点进行判断，若当前的点未染色，则染成一个颜色，然后对于相连接的点，都染成另一种颜色，若有相连的点已经有颜色，则进行判断，若是同一种颜色则不是二分图，返回false，若所有点染色都成功，则是二分图，返回true。循环是看是否所有点染色都成功，只要其中一次染色失败就是false。这所以这样做，是因为有些点之间可能不存在通路，所以要对所有点都进行染色。

#include<iostream>
#include<cstring>using namespace std;
const int N=1000010;
int h[N],e[N],idx=0,ne[N];
int col[N];
int m,n;void add(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}bool dye(int x,int c)
{   col[x]=c;for(int j=h[x];j!=-1;j=ne[j]){int t=e[j];if(!col[t]){if(!dye(t,3-c)){return false;}}else{if(col[t]!=3-c)return false;}}return true;
}int main()
{   memset(h,-1,sizeof h);scanf("%d%d",&n,&m);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}bool t=false;for(int i=1;i<=n;i++){   if(!col[i])if(!dye(i,1)){   t=true;break;}}if(t)puts("No");else puts("Yes");return 0;
}