二分图(染色法)

一、什么是二分图(二部图)？

定义：二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
换句人话来说：一个图的所有点可以划分为两个互不相交子集，并且图中每条边依附的两个点都分别属于这两个互不相交的子集，两个子集内的顶点不相邻。
下面这三个图就是二分图：

二、我们如何来辨别二分图呢？

根据定义来看，辨别二分图就是能否把图中的所有点分成两个独立的点集。
证明来看，如果一个图是二分图，那么该图必然不存在一个回路的长度为奇数。
因为一个图中如果存在一个回路并且这个回路的长度为奇数的话，那么这个回路中的点也应该为奇数。根据前面定义，每条边依附的两个点都分别属于这两个互不相交的子集，然而点数为奇数，所以肯定不可以划分成两个互不相交的子集。
比如下图就不是一个二分图，我们可以发现无论方框中的点为白色还是红色，都会让一条边依附的两个点在一个子集（颜色相同）。

这里我们利用染色法来判断二分图（深度优先搜索版本）

题目

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 u 和 v，表示点 u 和点 v 之间存在一条边。

输出格式
如果给定图是二分图，则输出

Yes

，否则输出

No

。

数据范围
1≤n,m≤10^5
输入样例：
4 4
1 3
1 4
2 3
2 4
输出样例：
Yes

这是一个非常基础的入门题，题目就是给我们一个图，让我们判断是否为二分图。

思路：

1. 染色可以使用1和2区分不同颜色，用0表示未染色。
2. 遍历所有点，每次将未染色的点进行深度优先搜索, 默认染成1或者2
3. 在这里我们不能判断某个点染色成功则说明该图是二分图，要判断某个点是否染色失败；染色失败则不是二分图，否则为二分图。

AC代码

#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>usingnamespace std;constint N=1e5+10,M=2*1e5+10;//无向图，边数*2int h[N],e[M],ne[M],idx;int color[N];int n,m;voidadd(int a,int b){//邻接表
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;}booldfs(int u,int c){
    color[u]=c;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!color[j]){if(!dfs(j,3-c))returnfalse;//如果当前j节点没有染色，就判断j节点染另一个颜色会不会出现矛盾，出现矛盾返回false(则不是二分图)}elseif(color[j]==c)returnfalse;//如果相邻的节点颜色相同，就不是二分图}returntrue;//如果没有染色失败则成功}intmain(){int a,b;memset(h,-1,sizeof h);scanf("%d%d",&n,&m);while(m--){scanf("%d%d",&a,&b);add(a,b);//无向图add(b,a);}bool flag=true;for(int i=1;i<=n;i++){if(!color[i]){if(!dfs(i,1)){
                flag=false;break;}}}if(flag)puts("Yes");elseputs("No");return0;}