一张图是二分图，当且仅当图中不存在奇数环。（集合内部没有边）
染色法判定二分图
给定一个n个点m条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条边。
输出格式
如果给定图是二分图，则输出“Yes”，否则输出“No”。
数据范围
1≤n,m≤10^5
输入样例：
4 4 1 3 1 4 2 3 2 4输出样例：
Yes #include <iostream> #include <algorithm> using namespace std; const int N = 100000+10; int head[N],nexts[N*2],ver[N*2]; int tot; int color[N]; void add(int x,int y){ ver[++tot]=y; nexts[tot]=head[x],head[x]=tot; } bool dfs(int x,int c){ color[x]=c; for(int i=head[x];i;i=nexts[i]){ int y=ver[i]; if(!color[y]&&!dfs(y,3-c)) return false; else if(color[y]==c) return false; } return true; } int main(){ int n,m; scanf("%d%d",&n,&m); while(m--){ int x,y; scanf("%d%d",&x,&y); add(x,y),add(y,x); } bool flag=true; for(int i=1;i<=n;i++){ if(!color[i]){//没有染色 if(dfs(i,1)==false){ flag=false; break; } } } puts(flag?"Yes":"No"); return 0; }
