Graphcoloring |-牛客（二分图判定）

Graphcoloring |

题意：

给一个无向完全连通图，试问这个图是不是二分图。假如是就输出各个点的染色情况。如果不是二分图就输出一个含奇数条边的环。

思路：

• 采用染色法，并用数组记录每个点的父节点。方便输出奇数条边的环。
• 其中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;
}