题意：
给一个无向完全连通图，试问这个图是不是二分图。假如是就输出各个点的染色情况。如果不是二分图就输出一个含奇数条边的环。
思路：
- 采用染色法，并用数组记录每个点的父节点。方便输出奇数条边的环。
- 其中vector数组vep存储的是点与点之间有边的关系。因为是无向图所以双向的。
- fa数组存储的是每个点的父节点。
#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;
}
