求助各位大佬,自己写了个二分图的判定的算法,目前没有找到反例,帮我这个小蒻蒟判断一下算法的正确性,以及优化,谢谢各位
#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";
}