图论 二分图

二分图:
将点集分为两部分 边只存在于两个集合之间
当且仅当 不存在奇数环

染色法 O(n+m)

因不存在奇数环 故染色过程中没有矛盾

//邻接表存储 无向图存储两边
const int N=1e5+5,M=2e5+10;
int h[N],e[M],ne[M],idx;
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int color[N];
int a,b;
int n,m;
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;
            }
        }
        else if(color[j]==c){
            return false;
        }
    }
    return true;
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    while(m--){
        cin>>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("No");
    }
    else{
        puts("Yes");
    }
    return 0;
}

匈牙利算法 O(m*n)

实际运行时间一般远小于O(m*n)

没有两条边公用一个节点就是完美匹配
数据保证 两个集合一定是二分图
求出二分图的 最大匹配数

int n1,n2,m;
const int N=510,M=2e5+10;
int h[N],e[M],ne[M],idx;
int n1,n2,m;
bool st[N];
int match[N];//右侧点在左侧的匹配点
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        //判断右侧的点
        if(!st[j]){
            st[j]=true;
            //未匹配or该左侧节点可以匹配另一个右节点
            if(!match[j]||find(match[j])){
                match[j]=x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    memset(h,-1,sizeof(h));
    cin>>n1>>n2>>m;
    while(m--){
        cin>>a>>b;
        add(a,b);
    }
    //匹配成功的对数
    int res=0;
    //遍历左侧的点
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof(st));
        if(find(i)){
            res++;
        }
    }
    cout<<res<<endl;
    retrurn 0;
}