USACO 2014 US Open Decorating The Pastures

题目大意：

给定n个点m条边的无向图

判断这个图能否将所有点依次染色为F J F J

若能输出最多能染多少个J

若不能输出-1

就是给一个图01染色 过程中判断是否出现不符合的情况

即点1到点2到点3到点1 这种奇数点环

即当发现下一个点已被染色且颜色与自己相同 就是-1

注意图可能是有多个分开的子图构成

每个子图染色为01后 答案加上多的一种

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define mem(i,j) memset(i,j,sizeof(i))
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define gcd(i,j) __gcd(i,j);
const int N=1e5+5;
const int mod=1e9+7;
const double eps=1e-8;

int n,m;
bool OK;

struct NODE { int to,nt; }e[N<<1];
int head[N], tot;
void init() { tot=1; mem(head,0); }
void addE(int u,int v) {
    e[++tot].to=v; e[tot].nt=head[u]; head[u]=tot;
}

int col[N], cnt[3];
void DFS(int u,int c) {
    if(OK==0) return ;
    col[u]=c; cnt[c]++;
    for(int i=head[u];i;i=e[i].nt) {
        int v=e[i].to;
        if(col[v]!=-1 && col[v]==col[u]) OK=0; // 子节点已被染色且与自己相同
        else if(col[v]==-1) DFS(v,!c); // 未被染色 继续搜染色
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m)) {
        init();
        while(m--) {
            int u,v; scanf("%d%d",&u,&v);
            addE(u,v); addE(v,u);
        }
        int ans=0;
        mem(col,-1); OK=1;
        for(int i=1;i<=n;i++) {
            if(col[i]!=-1) continue;
            mem(cnt,0); DFS(i,1);
            ans+=max(cnt[0],cnt[1]);
        }
        if(OK==0) printf("-1
");
        else printf("%d
",ans);
    }

    return 0;
}