学步园

题意：给定n个点m条边。这些边的意思为 u和v是相互仇恨的关系

要求满足一下条件。

1)一个人的周围不能有仇恨关系的人，这些人围成一个圆圈，每个点有两个邻居。

2)会议的是由三个人以上组成，开会议的人数必须是奇数。

要求出必须剔除几个人。

在做本题的过程中我查询了一些其他博客的做法。

本题需要的知识

1)补图(已知G求~G)

2)奇圈的定义(顶点个数为奇数的圈，但也有部分人说是边的个数为奇数的圈)

3)两个定理

1.如果一个双连通分量内的某些顶点在一个奇圈中（即双连通分量含有奇圈），那么这个双连通分量的其他顶点也在某个奇圈中；

2.如果一个双连通分量含有奇圈，则他必定不是一个二分图。反过来也成立，这是一个充要条件。

可以通过下面这个例子来理解这两定理

1-->2

1-->3

1-->4

3-->4

2-->4

{1,2,3,4}是一个点双连通分量，它有偶数个点，但是它有两个奇圈，能出席两次会议

4)求点双连通分量(tarjan相关算法的知识)

5)二分图的判定(交叉染色法)

其他：显然在只要某个点双连通分量不是二分图那么它必定包含奇圈，那么这个点双连通分量中的所有点都可以出席会议。由于割点一定属于某个强连通分量，如果直接算的话可能会算重，所以标记，最后一起算。

更详细内容见：http://blog.csdn.net/lyy289065406/article/details/6756821#quote

//author: CHC
//First Edit Time:	2014-07-10 20:09
//Last Edit Time:	2014-07-11 09:09
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 1010
vector <int> e[MAXN];
vector <int> bck[MAXN];
//vector <int> e1[MAXN];
int dfn[MAXN],low[MAXN],sta[MAXN*2];
int times,top;
int ssum,n,m;
char map1[MAXN][MAXN];
char can[MAXN];
char vis[MAXN];
char inbck[MAXN];
void tarjan_4(int u){
    sta[++top]=u;
    dfn[u]=low[u]=++times;
    for(int i=0;i<(int)e[u].size();i++){
        int v=e[u][i];
        if(!dfn[v]){
            tarjan_4(v);
            low[u]=min(low[u],low[v]);
            if(dfn[u]<=low[v]){
                do
                {
                    bck[ssum].push_back(sta[top]);
                }while(sta[top--]!=v);
                bck[ssum].push_back(u);
                ++ssum;
            }
        }
        else low[u]=min(low[u],dfn[v]);
    }
}
bool checkdfs(int u,int color){
    vis[u]=color;
    for(int i=0;i<(int)e[u].size();i++){
        int v=e[u][i];
        if(!inbck[v])continue;
        if(vis[v]==-1){
            if(!checkdfs(v,!color))return false;
        }
        else if(vis[u]==vis[v])return false;
    }
    return true;
}
void solve(){
    ssum=top=times=0;
    for(int i=0;i<MAXN;i++)bck[i].clear();
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(can,0,sizeof(can));
    for(int i=1;i<=n;i++)
        if(!dfn[i])tarjan_4(i);

    for(int i=0;i<ssum;i++){
        int tmp=bck[i].size();
        //if(tmp<3||tmp%2==0)continue;
        //if(tmp<3)continue;
        //for(int j=0;j<n+10;j++)e1[j].clear();
        memset(inbck,0,sizeof(inbck));
        for(int j=0;j<tmp;j++){
            inbck[bck[i][j]]=1;
        }
        /*
        for(int j=0;j<tmp;j++){
            int u=bck[i][j];
            inbck[u]=1;
        for(int k=j+1;k<tmp;k++){
            int v=bck[i][k];
            if(u==v)continue;
            if(map1[u][v])continue;
            e1[u].push_back(v);
            e1[v].push_back(u);
            //printf("%d -->%d\n",u,v);
        }
        }
        */
        memset(vis,-1,sizeof(vis));
        if(!checkdfs(bck[i][0],0)){
            //printf("yes\n");
            for(int j=0;j<tmp;j++){
                can[bck[i][j]]=1;
                //printf("%d\n",bck[i][j]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(!can[i])ans++;
    }
    printf("%d\n",ans);
}

int main()
{
    while(~scanf("%d%d",&n,&m)&&(n||m)){
        for(int i=0;i<n+10;i++)e[i].clear();
        memset(map1,0,sizeof(map1));
        for(int i=0,x,y;i<m;i++){
            scanf("%d%d",&x,&y);
            map1[x][y]=map1[y][x]=1;
        }
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            if(!map1[i][j])
            {
                e[i].push_back(j);
                e[j].push_back(i);
                //printf("%d-->%d\n",i,j);
            }

        solve();
    }
    return 0;
}