來(lái)源：牛客網(wǎng)：

題目描述

修修在黑板上畫(huà)了一些無(wú)向連通圖，他發(fā)現(xiàn)他可以將這些圖的結(jié)點(diǎn)用兩種顏色染色，滿足相鄰點(diǎn)不同色。
瀾瀾不服氣，在黑板上畫(huà)了一個(gè)三個(gè)點(diǎn)的完全圖。修修跟瀾瀾說(shuō)，這個(gè)圖我能找到一個(gè)簡(jiǎn)單奇環(huán)。
瀾瀾又在黑板上畫(huà)了一個(gè)n個(gè)點(diǎn)m條邊的無(wú)向連通圖。很可惜這不是一道數(shù)數(shù)題，修修做不出來(lái)了。
瀾瀾非常得意，作為一位毒瘤出題人，有了好題當(dāng)然要跟大家分享，于是他把這道題出給你做了。
輸入描述:
第一行兩個(gè)整數(shù)n,m (1≤ n,m≤ 3*105)，接下來(lái)m行每行兩個(gè)整數(shù)ai,bi表示一條邊 (1≤ ai,bi≤ n)。
保證圖連通，并且不存在重邊和自環(huán)。
輸出描述:

示例1
輸入
復(fù)制

3 2 1 2 1 3

輸出
復(fù)制

0 0 1 1

示例2
輸入
復(fù)制

3 3 1 2 1 3 2 3

輸出
復(fù)制

3 1 2 3

題解：

本題可以濃縮成兩個(gè)問(wèn)題：能否被01染色，以及是否有奇環(huán)，我們仔細(xì)想想會(huì)發(fā)現(xiàn)其實(shí)這兩個(gè)問(wèn)題是互相矛盾的，也就是能01染色就不存在奇環(huán)，反之亦然。所以題目中同時(shí)可行以及都不可行是不存在的
我們可以先01染色，當(dāng)發(fā)現(xiàn)染不動(dòng)時(shí)說(shuō)明就出現(xiàn)奇環(huán)了，記錄當(dāng)前不能再染的點(diǎn)（也就是染色矛盾的點(diǎn)），染色途中是記錄路徑的，所以輸出奇環(huán)時(shí)輸出路徑即可
額。。代碼沒(méi)有全對(duì)。。。

代碼：

#include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; const int N=3*1e5+50; vector<int> g[N]; int color[N]; int pre[N]; vector<int> res; bool flag; int root; void init(){memset(color,-1,sizeof(color));memset(pre,-1,sizeof(pre));flag=true; } void dfs(int v,int c){if(!flag){return;}color[v]=c;for(int i=0;i<g[v].size();i++){if(!flag){return;}pre[g[v][i]]=v;if(color[g[v][i]]==-1){dfs(g[v][i],c^1);}else{//不是二分圖if(color[g[v][i]]==c){flag=false;//說(shuō)明奇環(huán)就出現(xiàn)在這里root=g[v][i];return;}}} } int main(void){init();int n,m;int u,v;scanf("%d%d",&n,&m);for(int i=0;i<m;i++){scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0);if(flag){printf("0\n");for(int i=1;i<n;i++){printf("%d ",color[i]);}printf("%d\n",color[n]);}else{int now=pre[root];res.push_back(root);while(root!=now){res.push_back(now);now=pre[now];}int cnt=res.size();printf("%d\n",cnt);for(int i=0;i<cnt-1;i++){printf("%d ",res[i]);}printf("%d\n",res[cnt-1]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Graph Coloring I的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。