题目描述
给定一个n个点m条边的无向图,图中可能存在重边和自环。
请你判断这个图是否是二分图。
算法:深度优先搜索
时间复杂度:O(N+M)
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;
int n,m;
bool st[N];
int color[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u,int c)
{
color[u]=c;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(color[j]==-1){
if(!dfs(j,!c))
return false;
}
else if(color[j]==c)return false;
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
memset(color,-1,sizeof color);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
bool success=true;
for(int i=1;i<=n;i++){
if(color[i]==-1){
if(!dfs(i,0)){
success=false;
break;
}
}
}
if(success)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}