//二分图:图中不含奇数环 一条边两个点的颜色需不同 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int h[N],e[N],ne[N],idx; int col[N]; int n,m; void add(int a,int b) { e[idx]=b; ne[idx]=h[a]; h[a]=idx++; } bool dfs(int k,int s) { col[k]=s; for(int i=h[k];i!=-1;i=ne[i]) { int j=e[i]; if(!col[j]) { if(!dfs(j,3-s))return false; //若染色矛盾 返回错误 } else if(col[j]==s)return false; //矛盾:边上两点颜色一样 } return true; } int main(void) { memset(h,-1,sizeof h); cin>>n>>m; while(m--) { int a,b; cin>>a>>b; add(a,b); add(b,a); } bool fa=false; for(int i=1;i<=n;i++) { if(!col[i]) { if(!dfs(i,1)) { fa=true; break; } } } if(fa) puts("No"); else puts("Yes"); return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:612 |
C语言训练-计算1~N之间所有奇数之和 (C语言代码)浏览:681 |
【数组的距离】 (C语言代码)浏览:775 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:904 |
WU-C语言程序设计教程(第三版)课后习题12.1 (C++代码)浏览:1016 |
有关字符,字符串的输入输出函数说明浏览:493 |
剪刀石头布 (C++代码)浏览:1800 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:716 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:748 |
DNA (C语言代码)浏览:833 |