图论—二分图(更新中。。。

admin2024-04-03  0

染色法判定二分图

一个图是二分图当且仅当图中不含有奇数环。我们可以用染色法判断一个图是不是二分图。如果二分图能够被完美染色,那么它就是二分图,否则不是。染色的过程可以用DFS完成。对于某一个点,我们把他染色为A,那么第一个和它相邻的点的颜色就染色为B,下一个是A,以此类推,可知该条通路上的所有点的颜色都确定。

图论—二分图(更新中。。。,第1张

如图为一个二分图,两个组内部之间没有连线,一个点所连的另外两个点与该点不在一个组内,两个点之间颜色不一样。 

染色法判定二分图题目链接

#include <bits/stdc++.h>
using namespace std;
const int N =1e5+5;
vector<int>g[N];
int n,m;
int color[N];

bool dfs(int x,int c){
    color[x]=c;//先染上该颜色
    for(const auto &y:g[x]){
        if(!color[y]){
            if(!dfs(y,3-c))return false;//如果下一个不是另一个颜色
        }
        else if(c==color[y]){//和相邻元素颜色一样则false
            return false;
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bool flag=true;
    for(int i=1;i<=n;i++){
        if(!color[i]){
            if(!dfs(i,1)){//取i点颜色为1
                flag=false;
                break;
            }
        }
    }

    if(!flag)cout<<"No"<<"\n";
    else cout<<"Yes"<<"\n";

    return 0;
}

二分图的最大匹配(匈牙利算法)

图论—二分图(更新中。。。,第2张

如图:求最大匹配的对象数量

首先男1选1,男2选2,男3只能选1或者2,那么再看看女1的对象男1,男1可以喜欢2,但是2有人喜欢了,所以不行,再看看男二,他可以喜欢女3,此时没人选,那么3选3,轮到男4选,此时所有的女生都有人了,所以就不能配对成功。最大匹配数为3。

二分图的最大匹配题目链接

#include <bits/stdc++.h>
using namespace std;
const int N =1e5+5;
int n1,n2,m;
vector<int>g[N];
bool st[N];//表示这个女孩有没有对象(防止重复选)
int match[N];//match[i]=j表示i这个女孩现在男友是j

bool find(int x){
    //遍历自己喜欢的女孩
    for(const auto &y:g[x]){
        if(!st[y]){
            st[y]=true;//预定
            //如果y没有对象,或者y现有的对象有其他喜欢的人
            //那么x可以选择y
            if(!match[y]||find(match[y])){
                match[y]=x;
                return true;
            }
        }
    }
    //全部都被预定了
    return false;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n1>>n2>>m;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        g[x].push_back(y);//男生到女生牵红线
    }

    int ans=0;
    for(int i=1;i<=n1;i++){
        memset(st,false,sizeof(st));//每次遍历初始化
        if(find(i)){//如果男生找到对象
            ans++;
        }
    }

    cout<<ans<<"\n";

    return 0;
}

(ps:为什么st数组每次循环一遍男生都要初始化:因为要判断该男生能不能从已经有对象的女生中选择,如果该女生对象有其他喜欢的人,那么循环到的男生就和这个女生处对象。)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!