poj-2942-点双联通

题意：

亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。

如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议？

注意：1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。
2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。即每个骑士的座位两边都必定各有一个骑士。
3、一个骑士无法开会，就是说至少有3个骑士才可能开会。

做法：

1，先对憎恶关系建图

2，建立上图的反图，这时候，图表明的关系是可以坐在一起。

3，求图中所有点大于等于3的圈。（tarjan求点双连通）

4，求3的求出的圈是不是奇圈。（交叉染色法）

#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 1001
#define maxm 1000005
vectorvc[maxn];
stackst;
vectorvec;
int maps[maxn][maxn];
int n,m;
struct list
{
    int u;
    int e;
    int next;
}edge[maxm*2];
int tops,head[maxm*2],vis[maxm*2];
int nums,dnf[maxn],low[maxn],instack[maxn],times;
int mark[maxn],odd[maxn],visit[maxn];;
void add(int x,int y)
{
   // printf("%d---%d %d\n",tops,x,y);
    edge[tops].u=x;
    edge[tops].e=y;
    edge[tops].next=head[x];
    head[x]=tops++;
}
void init()
{
    int a,b,i,j;
    for(i=0;i<=n;i++)
        for(j=0;j<=n;j++)
            maps[i][j]=0;
    for(i=0;idos(int x)
{
    int i;
    memset(visit,-1,sizeof(visit));
    visit[x]=0;
    if(find(x))
    {
        for(i=0;i<=n;i++)
        if(mark[i])odd[i]=1;
    }
}
void tarjan(int x)
{
    int i;
    low[x]=dnf[x]=times++;
    for(i=head[x];i!=-1;i=edge[i].next)
    {
        if(vis[i])continue;
        vis[i]=vis[i^1]=1;
        int y=edge[i].e;
       // printf("%d-%d----\n",x,y);
        if(!dnf[y])
        {
            st.push(i);
            tarjan(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dnf[x])
            {
                memset(mark,0,sizeof(mark));
                int yw=0;
                int cc=0;
                while(1)
                {
                    cc++;
                    yw=st.top();
                    st.pop();
                    //printf("%d ",yw);
                    mark[edge[yw].e]=mark[edge[yw].u]=1;
                    if(edge[yw].u==x)break;
                }
               // cout<=3)dos(x);
            }
        }
        else if(dnf[y]