用dfs对图染色,如果不冲突则第一种情况输出
如果冲突则退出进入奇数环判断(第二种情况)
不可能两种情况都不满足
#include<bits/stdc++.h> using namespace std; struct oppo { int to,next; } rood[600005]; int head[300005],tot; void add(int from,int to) { rood[++tot].to=to; rood[tot].next=head[from]; head[from]=tot; } int n,m; int s,t; int f[300005]; bool dfs(int x) { for (int i=head[x];i;i=rood[i].next) { if(f[rood[i].to]==-1) { f[rood[i].to]=!f[x]; if(dfs(rood[i].to)==0) return 0; } else if(f[rood[i].to] != !f[x]) return 0; } return 1; } int js=0; queue<int> v; void ddd(int x,int fa) { if(f[x]) { if(((f[fa]-f[x])&1)==0) js=x; return; } f[x]=f[fa]+1; for (int i=head[x];i;i=rood[i].next) { if(rood[i].to==fa) continue; ddd(rood[i].to,x); if(js) { if(js==-1) return; v.push(x); if(js==x) js=-1; return; } } f[x]=0; } int main() { cin>>n>>m; for (int i=1;i<=m;i++) { cin>>s>>t; add(s,t); add(t,s); } memset(f,-1,sizeof(f)); f[1]=0; if(dfs(1)) { puts("0"); for (int i=1;i<=n;i++) cout<<f[i]<<" "; } else { memset(f,0,sizeof(f)); ddd(1,0); cout<<v.size()<<"\n"; while(v.size()) { cout<<v.front()<<" "; v.pop(); } } return 0; }