染色法判断二分图
二分图：
一个无向图，使得顶点集V可以分割为两个互不相交的子集A,B，使得所有边两端分别属于两个子集A,B。
要判断二分图，要分两种情况，一种是联通图，一种是非连通图，两者都不难。
大致思路就是先找到一个没被染色的节点u，把它染上一种颜色，之后遍历所有与它相连的节点v，如果节点v已被染色并且颜色和节点u一样，那么就失败了。如果这个节点v没有被染色，先把它染成与节点u不同颜色的颜色，然后遍历所有与节点v相连的节点............就这样循环下去，直到结束为止。
连通图代码：
1 #include2 #include 3 #define N 42000 4 int next[N],to[N],num,head[N],col[N],flag,n,m,a,b; 5 void add(int false_from,int false_to){ 6 next[++num]=head[false_from]; 7 to[num]=false_to; 8 head[false_from]=num; 9 }10 void dfs(int x,int color){11 col[x]=color;12 for(int i=head[x];i;i=next[i]){13 if(col[to[i]]==col[x]){14 printf("NO");15 flag=1;16 exit(0);17 }18 if(!col[to[i]])19 dfs(to[i],-color);20 }21 }22 int main(){23 scanf("%d%d",&n,&m);24 for(int i=1;i<=m;++i){25 scanf("%d%d",&a,&b);26 add(a,b);27 add(b,a);28 }29 dfs(1,1);30 if(!flag)31 printf("YES");32 return 0;33 }
非连通图代码：
1 #include2 #include 3 #define N 42000 4 int next[N],to[N],num,head[N],col[N],flag,n,m,a,b; 5 void add(int false_from,int false_to){ 6 next[++num]=head[false_from]; 7 to[num]=false_to; 8 head[false_from]=num; 9 }10 void dfs(int x,int color){11 col[x]=color;12 for(int i=head[x];i;i=next[i]){13 if(col[to[i]]==col[x]){14 printf("NO");15 flag=1;16 exit(0);17 }18 if(!col[to[i]])19 dfs(to[i],-color);20 }21 }22 int main(){23 scanf("%d%d",&n,&m);24 for(int i=1;i<=m;++i){25 scanf("%d%d",&a,&b);26 add(a,b);27 add(b,a);28 }29 for(int i=1;i<=n&&!flag;++i)30 if(!col[i])31 dfs(i,1);32 if(!flag)33 printf("YES");34 return 0;35 }
后记：本来都搞过这东西了，然而培训时听某清北奆佬讲到这，以为要搞更diao的东西，于是一激动就把原来那篇给删了，尽管补一篇不难，但是.........................................................