二分图：染色法、匈牙利算法

5.二分图：染色法、匈牙利算法

二分图：可以将一个图中的所有点，分成左右两部分，使得图中的所有边，都是从左边集合中的点，连到右边集合中的点。而左右两个集合内部都没有边。

再通俗点理解：一个图是二分图当且仅当图中不含奇数环（奇数环：边数为奇数的环）

（一）染色法—判断二分图

对每一个点进行染色操作，只用黑白两种颜色；用dfs和bfs两种方式去实现,对图进行遍历并染色。时间复杂度为O(n+m)

二分图一定不含奇数环，不含奇数环的图一定为二分图

**充分性：**如果图中存在奇数环（构成环的顶点数量是奇数），那一定不是二分图），下图可以看到，依次选一个点，进行染色（原则是相邻的点要染于该点不同色），奇数环的染色结果会出现矛盾。；

**必要性：**如果没有奇数环，那么剩下的点的关系就是：偶数环or单链。这两种情况都能保证同一条边上相邻顶点在不同集合中，所以也是成立的；

综上：只要在染色过程中不存在矛盾（这里用黑白进行染色，即一个点不能即为黑色，又为红色），整个图遍历完成之后，所有顶点都顺利染上色。就说明这是一个二分图

AcWing 860. 染色法判定二分图

**实现思路：**这里使用深度优先遍历DFS实现（代码相比BFS短点）

使用邻接表存储图
使用一个数组color代表当前点的染色，若为-1则未染色，若为0则为白色，若为1则为黑色
设置一个标志变量flag判断是否矛盾。然后循环遍历各点，若未染色则进行染色（染为0或1），对该点再进行深度优先遍历，对其连通的点进行判断。
- 若未染色，则染上与该点相反的颜色；若已染色，判断是否与当前点的颜色相同。
  - 若相同则出现矛盾，提前返回false，得到结果不是二分图。否则继续遍历判断、染色
直到循环结束，判断标志变量flag，为真则为二分图

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10,M=2*N;
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++;
}
 
//深度优先遍历染色 若出现矛盾返回false
bool dfs(int u,int c){//u表示结点,c表示染色种类 未染-1 白0 黑1
    color[u]=c;//先染色
    //给相连点染色
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(color[j]==-1){//未染色
            if(!dfs(j,!c)) return false;//染上相反色，且对其继续深度遍历染色其他结点直至返回false出现矛盾
        }eles if(color[j]==c) return false;//若已经染色 且和当前颜色相同 则矛盾
    }
    return true;//未出现矛盾
}
 
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(color,-1,sizeof color);//初始化一下染色数组
    
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);//无向图
    }
    
    bool flag=true;//判断是否是二分图
    for(int i=1;i<=n;i++){
        if(color[i]==-1){//未染色
            if(!dfs(i,1)){//染色 然后深度遍历染色
                flag=false;//出现矛盾 不是二分图
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    return 0;
}

（二）匈牙利法—二分图的最大匹配

二分图的最大匹配：

匹配（本质是一个边的集合！）给定一个二分图S，在S的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
极大匹配

极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。（也就是说，再加入任意一条不在匹配集合中的边，该边肯定有一个顶点已经在集合中的边中了）
最大匹配

所有极大匹配当中边数最大的一个匹配

下图是一个最大匹配（黄色边）

通俗一点的理解：

**匈牙利算法：**两个集合中都存在一些点，以左集合出发，查找两个集合之中匹配成功的点的个数。如果左集合的某一个点发现与自己相连的节点已经被占有，则查询占有该节点的左集合的点是否有其他可配对的点，若有则两全其美，否则继续寻找，若仍未找到，则配对失败。时间复杂度理论上是O(nm)，但实际运行时间一般远小于O(nm)。

通俗点说：从左边开始，左边a喜欢右边b（即两者有连线），若b此时没有已经匹配的人或者即便有匹配的人，那个匹配的对象可以找到其他人（下家）来配对，即把b让给a，则a与b匹配成功。若两种情况下都不满足，则a只能找下一个有好感的人尝试匹配，直至匹配成功或已经没有喜欢的了。进行下一个人的匹配，最终得到的匹配对数即为二分图的最大匹配对

更加详细的理解：【二分图算法】手把手教你学会：染色法（判断二分图）、匈牙利算法（二分图的最大匹配）_二分图染色的原理-CSDN博客

AcWing 861. 二分图的最大匹配

实现思路：

使用邻接表存储图。以左边集合为主，每个点可能与多个点相连（存在多个可能的匹配）
设置一个判重数组s[]，s[i]为真表示i结点已经被当前结点尝试过，每次换一个人都要把数组s[]重置为false；设置一个匹配数组match[]，为0表示当前结点还没有匹配的对象，否则为匹配对象的编号
find函数（找匹配对象）：每次对相连的点尝试匹配，若当前连接点未尝试过，则尝试；若该点没有匹配对象或者他的匹配对象可以把该结点让给我，则与之匹配，退出匹配成功，下一个继续

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=510,M=1e5+10;
int h[N],ne[M],e[M],idx;
int match[N];//匹配数组
bool s[N];//判重数组
int n1,n2,m;
 
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
 
//找到x的匹配对象
bool find(int x){
    //遍历相连的点
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        if(!s[j]){//还没尝试过 则尝试
            s[j]=true;
            //如果没有对象或者她对象有下家可以把她让给你
            if(match[j]==0 || find(match[j])){
                match[j]=x;
                return true;//匹配成功
            }
        }
    }
    return false;//尝试下来 匹配失败
}
 
 
int mian(){
    cin>>n1>>n2>>m;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);//虽然是无向图，但只从一边的集合开始遍历，不用反过来再存储一遍了
    }
    
    int cnt=0;//记录最大匹配对数
    for(int i=1;i<=n;i++){
        memset(s,false,sizeof s);//每次给一个点匹配时，先将s置false 表示都还没尝试
        if(find(i)) cnt++;//i找到对象了
    }
    cout<<cnt;
    return 0;
}

编程笔记

探索