二分图(染色法)

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

定义：二分图又称作二部图，是图论中的一种特殊模型。 设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 
#include 
#include 
#include 
using namespace std;

const int N=1e5+10,M=2*1e5+10;  //无向图，边数*2

int h[N],e[M],ne[M],idx;
int color[N];
int n,m;

void add(int a,int b){   //邻接表
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

bool dfs(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)) return false;  //如果当前j节点没有染色，就判断j节点染另一个颜色会不会出现矛盾，出现矛盾返回false(则不是二分图)
        }
        else if(color[j]==c) return false;  //如果相邻的节点颜色相同，就不是二分图
    }
    return true;   //如果没有染色失败则成功
}

int main(){
    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");
    else puts("No");
    return 0;
}