二分图

都是无向图！！！！！！！

关于二分图的知识点

二分图的定义

把所有的点分成两个集合
使得所有的边都在集合之间
集合内部没有边
想象程序员和编程语言的匹配，男人和女人匹配

性质

一个图是二分图当且仅当图中不含奇数环
奇数环：环当中的边的数量是奇数

染色法判定二分图

AcWing 860. 染色法判定二分图

如果一个图在染色的过程中没有矛盾，那就是一个二分图；如果染着染着发生矛盾了，那就不是二分图

在一个连通块中，只要有一个点的颜色确定了，那么整个连通块的颜色就都可以确定了！！！

没有环的无向图要么是树，要么是森林（多棵树）

树天然是可以“黑白染色”的：从根节点开始交替染色，相邻的点颜色一定不同。所以你可以把所有点分成两个集合，这就构成了一个标准的二分图结构

一些感想

以dfs深度优先搜索的顺序在染色，在递归的时候除了调用dfs染子节点，还要根据返回值判断当前dfs的返回值是不是false

我在手工演示的时候会习惯用宽搜的那种顺序，代码的实现是深搜的顺序

主函数中

多次调用是因为一个无向图不一定连通
每次对一个新子图的点进行第一步染色时，直接指定染成1就好了

易错点

1.记得break

bool flag=true;
for(int i=1;i<=n;i++){
    if(color[i]==0){
        if(dfs(i,1)==false){
            flag=false;
            break;
            //记得break，因为有一个子图不是连通图 
            //那么整个图就不是连通图
            //如果没有break
            //结果可能被后面的子图的结果覆盖了 
        }
    }
}

2.记得memset()

memset(h,-1,sizeof h);

一开始我忘记写了，没想到竟然不是死循环，而是输出了错误结果
导致找了好久的错误没找到

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+7;

int n,m;

int h[N],e[N*2],ne[N*2],idx;

int color[N];//0表示还没染色，1，2分别表示一种色 

void insert(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool dfs(int u,int col)
{
    color[u]=col;

    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(color[j]==0){
            if(dfs(j,3-col)==false) return false;
        }else{
            if(color[j]==col) return false; 
        }
    }

    return true;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);//别忘了 

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        insert(u,v);insert(v,u);
    }

    bool flag=true;
    for(int i=1;i<=n;i++){
        if(color[i]==0){
            if(dfs(i,1)==false){
                flag=false;
                break;
                //记得break，因为有一个子图不是连通图 
                //那么整个图就不是连通图
                //如果没有break
                //结果可能被后面的子图的结果覆盖了 
            }
        }
    }

    if(flag==true) printf("Yes\n");
    else printf("No\n");

    return 0;
}

二分图的最大匹配

AcWing 861. 二分图的最大匹配
P3386 【模板】二分图最大匹配

二分图的匹配

找一些边，使得不同边所连接的点是不同的
可以想成：横着一条一条地放置

二分图的最大匹配

边数最大的一种匹配方法

性质

二分图的最大匹配不一定是唯一的

匈牙利算法思想

关键理解点

1.当后面男生矛盾时，前面男生能退让的话就会退让，如果没法退让，是前面的男生选中的结果优先
2.在看是否能退让的过程中，是后面的男生通过设置st为true实现了优先
原因：
在退让的过程中（尝试着挪动前面的布局给后面的男生让出女生时），后面男生是把st先设为true了，因此前面男生一旦遇到st是true，就会直接略过了。其实也合理，不然如果遇到st是true还不略过，那就有双挪动了，整个局面边复杂很多
3.尽量创造机会，没机会了也没办法

易错点

1.记得main中记得每次考虑find(i)之前，都得把st全设置为false

#include <bits/stdc++.h>
using namespace std;

const int N=507;
const int M=1e5+7;

int n1,n2,m;
int h[N],e[M],ne[M],idx;

//st和match的下标都是指的女生 
bool st[N]; 
int match[N];

int ans;


void insert(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}


bool find(int u)
{
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(st[j]==false){
            st[j]=true;
            if(match[j]==0||find(match[j])==true){
                match[j]=u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d%d",&n1,&n2,&m);
    memset(h,-1,sizeof h);

    for(int i=1;i<=m;i++){
        int u,v;scanf("%d%d",&u,&v);
        insert(u,v);
    }

    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof st);
        if(find(i)==true) ans++; 
    }

    printf("%d\n",ans);

    return 0;
}