染色法判断二分图

$$染色法判定二分图$$

二分图

首先什么是二分图呢？这里的$二分指的是点的二分和边两侧点的二分$。

1. $点的二分$：给定一个图，图中的点必须放置在两个互不相交的集合之中。
   

2. $边两侧点的二分$：两个集合$S1$和$S2$中的点已经分好了，如果存在一条边连接两个点，那么这两个点必须都是$不同$集合的。
   
   图中蓝线都是正确的，灰线是不可以存在的。

有关二分图的一些基础知识

如何判断一个无向图是否是二分图？根据二分图的定义，可以用两个颜色来标志两个集合，对每个点进行染色，看是不是所有的点都能“正确”的染色。如果可以那么就是二分图，否则就不是。

$二分图当且仅当中不含奇数环$
假如图中含有一个奇数环($环形结构的点数为奇数$)

上图中就有一个奇数环。假设图中$A$节点涂的是“左”颜色，根据二分图定义，相连的$B$节点颜色应该涂“右”颜色，继续推理$C$节点应该涂“左”颜色，环形结构循环之后，推出了$A$颜色应该是“右”颜色，与一开始的假设不符。所以原假设成立。

算法抽象模拟

涂色流程可以使用一个二叉树来进行表示：

左侧是将二分图涂色抽象为一个二叉树操作，右侧是涂色错误的情况：两个相连的点涂了一种颜色(在同一个集合中)。
二叉树操作重复度很高，可以使用$DFS$深搜进行涂色操作。

算法流程

bool DFS(int u,int c)
{
    对当前点u进行涂色
    
    for(遍历u点所连的所有点)
    {
        if(当前点没有涂色)
        {
            DFS(当前点，另一种颜色)
            判断对于当前点染色是否成功
        }
        //当前点染色情况
        else if(当前遍历点染色 == u点染色)
            判断是否成功
    }
    
    染色成功
}

完整代码

#include 
#include 
#include 

using namespace std;

const int N = 100010 , M = 200010;

int n,m;
int h[N] , e[M] , ne[M] , idx;          //存储无向图的时候e与ne开的大小应该是二倍，需要存储双向的边
int color[N];                           //颜色标记

void add(int a,int b)           //近邻表存储无向图的add
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool DFS(int u,int c)           //返回值是是否成功染色
{
    color[u] = c;           //开始的时候将u点染色成为c颜色
    
    for(int i = h[u] ; i != - 1 ; i = ne[i])        //遍历u点所连接的其他点
    {
        int j = e[i];
        
        if(!color[j])                       //如果这个点没有染色
        {
            if(!DFS(j,3-c))                 //DFS调用染个其他颜色看是否成功
                return false;
        }
        
        else if (color[j] == c)             //如果这个点染的颜色和u点的染色情况相同，那么染色失败
            return false;
    }
    
    return true;                        
}


int main()
{
    cin >> n >> m;
    
    memset(h,-1,sizeof(h));             //近邻表头初始化
    
    while(m--)                  //加入所有的边
    {
        int a,b;
        
        cin >> a >>b;
        
        add(a,b);
        add(b,a);
    }
    
    bool flag = true;               //设定一个flag标志整体染色之后有没有成功
    
    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;
}