CodeForces 688C NP-Hard Problem

題目連結：

http://codeforces.com/problemset/problem/688/C

題意：

給你一系列的點，以及一系列點之間的關系，問你這些點能不能構成二分圖。

題解：

一道很好的判斷二分圖的題目，這裡應用到了二分圖的一個性質，如果圖中有環出現，并且環的長度為奇數，那麼它必然不會構成二分圖，這裡其實可以使用染色的方法去做。

代碼：

#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define met(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
const int maxn = +;
vector<int> p[maxn];
vector<int> pp[];
int color[maxn];
bool flag=false;

void dfs(int x,int c)
{
    if(flag)
        return;
    if(color[x]!=-)
    {
        if(color[x]!=c)
            flag=true;
        return;
    }
    color[x]=c;
    pp[c].push_back(x);
    for(int i=;i<p[x].size();i++)
        dfs(p[x][i],c^);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        p[x].push_back(y);
        p[y].push_back(x);
    }
    met(color,-);
    for(int i=;i<=n;i++)
    {
        if(color[i]==-)
            dfs(i,);
    }
    if(flag)
    {
        cout<<-<<endl;
        return ;
    }
    cout<<pp[].size()<<endl;
    for(int i=;i<pp[].size();i++)
    {
        if(i!=pp[].size()-)
            printf("%d ",pp[][i]);
        else
            printf("%d\n",pp[][i]);
    }
    cout<<pp[].size()<<endl;
    for(int i=;i<pp[].size();i++)
    {
        if(i!=pp[].size()-)
            printf("%d ",pp[][i]);
        else
            printf("%d\n",pp[][i]);
    }

}