给定一个n个点m条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n和m。
接下来m行,每行包含两个整数u和v,表示点u和点v之间存在一条边。
输出格式
如果给定图是二分图,则输出“Yes”,否则输出“No”。
数据范围
1≤n,m≤105
输入样例:
4 4
1 3
1 4
2 3
2 4
输出样例:
Yes
二分图,没有奇数条边环的图
//染色法判断二分图
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+10;
ll h[N],ne[N],e[N],idx;
ll color[N];
ll m,n;
void add(ll a,ll b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(ll u,ll c)
{
color[u]=c;
for(ll i=h[u];i!=-1;i=ne[i])
{
ll 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;
for(ll i=0;i<m;i++)
{
ll a,b;cin>>a>>b;
add(a,b);add(b,a);
}
ll find=1;
for(ll i=1;i<=n;i++)
{
if(!color[i]) //没有被染色;
{
if(!dfs(i,1)) //染色加判断;
{
find=0;
break;
}
}
}
if(find)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}