题解 | #Graph Coloring I#

思路

无非就两种情况：可二涂色或者存在奇环。
那么我们在dfs的过程中留意有无涂色不符的情况，
没有发现就直接输出一种涂色方案就行了。
现在问题就是找到奇环该怎么输出呢？
因为我是个笨比所以一开始写了个tarjan记录SCC，
然后去输出第一个奇数并大于1个点的SCC的每一个点编号，
结果只过了45.45%（所以看代码的时候请忽略没删的多余变量吧）
实际上我们对一个点访问第二次的时候发现它涂色不符，就
可以确定我们前面遍历了一个环，而这个环就是奇环，并且在栈中是连续的。
我们只需要按照入栈顺序进行输出即可。(写了tarjan还是有所启发的)

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=300007;

int n,m,u,v,flag;
int head[maxn],cnt;
int col[maxn],vis[maxn];
int dfn[maxn],low[maxn],sz[maxn],bel[maxn];
int stk[maxn],top,idx,sccnum;
vector<int>scc[maxn];

struct E{
    int next,to;
}e[maxn<<1];

void addedge(int from,int to){
    e[++cnt].next=head[from];
    e[cnt].to=to;
    head[from]=cnt;
}

void dfs(int x,int fa,bool c){
    if(dfn[x]){ //已经访问过该节点 
        if(dfn[x]<top&&col[x]!=c){ //如果在栈中并且颜色不符 
            printf("%d\n",top-dfn[x]+1); 
            for(int i=dfn[x];i<=top;i++) printf("%d ",stk[i]); 
            exit(0);    
        }
        return;
    }
    stk[++top]=x,dfn[x]=top; //入栈，用桶存栈下标
    col[x]=c;
    for(int i=head[x];i;i=e[i].next){
        if(e[i].to!=fa){
            dfs(e[i].to,x,!c);
        }
    } 
    --top;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    }
    dfs(1,0,0);
    cout<<0<<endl;
    for(int i=1;i<=n;i++) cout<<col[i]<<" "; 
    return 0;
}