求助二分图判定
  • 板块学术版
  • 楼主adc1313
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/2/22 18:06
  • 上次更新2023/10/24 00:06:16
查看原帖
求助二分图判定
731561
adc1313楼主2023/2/22 18:06

求助各位大佬,自己写了个二分图的判定的算法,目前没有找到反例,帮我这个小蒻蒟判断一下算法的正确性,以及优化,谢谢各位

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

unordered_set<int>a;
unordered_set<int>b;
int m,n;
int mapp[2][200];

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        mapp[0][i]=x;
        mapp[1][i]=y;
    }
    a.insert(mapp[0][0]);// 初始化
    b.insert(mapp[1][0]);
    for(int i=0;i<m;i++){
        auto x=mapp[0][i],y=mapp[1][i];
        if((a.count(x)==1&&a.count(y)==1)||(b.count(y)==1&&b.count(x)==1)){
            cout<<"NO";
            exit(0);
        }//判断两个数是否在同一个集合
        if((a.count(x)==0&&b.count(y)==0)||(a.count(y)==0&&b.count(x)==0)){
            a.insert(x);
            b.insert(y);
        }//如果两个集合都没有,加数
        if(a.count(x)==1||b.count(x)==1){
            if(a.count(x)==1)b.insert(y);
            if(b.count(x)==1)a.insert(y);
        }
        if(a.count(y)==1||b.count(y)==1){
            if(a.count(y)==1)b.insert(x);
            if(b.count(y)==1)a.insert(x);
        }//如果任意一个集合有其中一个数,把另一数加到另一个集合
        for(int j=0;j<m;j++){
            if(j==i)continue;
            auto z=mapp[0][j],w=mapp[1][j];
            if((a.count(z)==1&&a.count(w)==1)||(b.count(w)==1&&b.count(z)==1)){
                cout<<"No";
                exit(0);
            }//如果z,w在同一个集合,则不是二分图
            if(a.count(z)==1||b.count(z)==1){
                if(a.count(z)==1)b.insert(w);
                if(b.count(z)==1)a.insert(w);
            }
            if(a.count(w)==1||b.count(w)==1){
                if(a.count(w)==1)b.insert(z);
                if(b.count(w)==1)a.insert(z);
            }//同上
        }
    }
    cout<<"Yes";
}
2023/2/22 18:06
加载中...