題意：
給一個(gè)無(wú)向完全連通圖肺魁，試問(wèn)這個(gè)圖是不是二分圖。假如是就輸出各個(gè)點(diǎn)的染色情況隔节。如果不是二分圖就輸出一個(gè)含奇數(shù)條邊的環(huán)鹅经。
思路：
- 采用染色法寂呛，并用數(shù)組記錄每個(gè)點(diǎn)的父節(jié)點(diǎn)。方便輸出奇數(shù)條邊的環(huán)瘾晃。
- 其中vector數(shù)組vep存儲(chǔ)的是點(diǎn)與點(diǎn)之間有邊的關(guān)系贷痪。因?yàn)槭菬o(wú)向圖所以雙向的。
- fa數(shù)組存儲(chǔ)的是每個(gè)點(diǎn)的父節(jié)點(diǎn)蹦误。
#include<bits/stdc++.h>
#define M 300010
using namespace std;
vector<int>vep[M];
int color[M];
int fa[M];
int n,m;
int flag;
int father,son;
void init( )
{
for(int i=0;i<=n;i++)
{
vep[i].clear( );
color[i]=-1;
fa[i]=-1;
}
flag=1;
son=-1;
father=-1;
}
void dfs(int x,int k)
{
color[x]=k;
for(int i=0;i<vep[x].size( );i++)
{
int v=vep[x][i];
if(color[v]==-1)
{
fa[v]=x;
dfs(v,(k+1)%2);
}
else if(color[x]==color[v])
{
father=x;
son=v;
flag=0;
return ;
}
}
}
int main( )
{
scanf("%d%d",&n,&m);
init( );
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
vep[x].push_back(y);
vep[y].push_back(x);
}
dfs(1,1);
if(flag)
{
//cout<<son<<" "<<father<<endl;
cout<<0<<endl;
for(int i=1;i<=n;i++)
{
printf("%d ",color[i]);
}
}
else
{
/* cout<<son<<" "<<father<<endl;
for(int i=1;i<=n;i++)
{
cout<<fa[i]<<" ";
}
cout<<endl;*/
queue<int>a;
while(son!=father)
{
a.push(son);
son=fa[son];
}
a.push(father);
cout<<a.size( )<<endl;
while(!a.empty( ))
{
printf("%d ",a.front( ));
a.pop( );
}
}
printf("\n");
return 0;
}
