Graph Coloring I

用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;
}