题意：一些骑士，他们有些人之间有矛盾，现在要求选出一些骑士围成一圈，圈要满足如下条件：1.人数大于1。2.总人数为奇数。3.有仇恨的骑士不能挨着坐。问有几个骑士不能和任何人形成任何的圆圈。
思路：首先反向建立补图，然后问题转换成在图中找奇圈，圈肯定出现在双联通分量中，则求出图的双联通分量，又通过特性知道，一个双联通分量有奇圈则其中的点都可以出现在一个奇圈中。而对于奇圈的判定可以用交叉染色判断是非为二分图，二分图中肯定无奇圈，这里用tarjan算法得出割边（先将点入队），确定双联通分量的根节点，(对于队列中的点)然后进行染色判定，最后标记odd[]代表需要删除的点。
代码：
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 1004
#define MAXM 1001000 int n,m,tot,count,top;
int first[MAXN],DFN[MAXN],Low[MAXN],vis[MAXN],col[MAXN],mark[MAXN],stack[MAXM],odd[MAXN];
int G[MAXN][MAXN];
struct Edge
{
int st,to,next,vis;
}edge[2*MAXM];
void addedge(int a,int b)
{
edge[tot].to=b;
edge[tot].st=a;
edge[tot].next=first[a];
edge[tot].vis=0;
first[a]=tot++;
}
int find(int s)
{
for(int i=first[s];i!=-1;i=edge[i].next)
{
int t=edge[i].to;
if(mark[t])
{
if(col[t]==-1)
{
col[t]=!col[s];
return find(t);
}
else if(col[t]==col[s]) return 1;
}
}
return 0;
}
void color(int s)
{
int i;
memset(mark,0,sizeof(mark));
do{
i=stack[top--];
mark[edge[i].st]=1;
mark[edge[i].to]=1;
}while(edge[i].st!=s);
memset(col,-1,sizeof(col));
col[s]=0;
if(find(s))
{
for(int i=1;i<=n;i++)
{
if(mark[i])
odd[i]=1;
}
}
}
void dfs(int s)
{
DFN[s]=Low[s]=++count;
for(int i=first[s];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].vis)continue;
edge[i].vis=edge[i^1].vis=1;
stack[++top]=i;
if(!DFN[v])
{
dfs(v);
Low[s]=min(Low[s],Low[v]);
if(Low[v]>=DFN[s])color(s);
}
else
{
Low[s]=min(Low[s],DFN[v]);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m),n||m)
{
memset(G,0,sizeof(G));
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
G[a][b]=1;
G[b][a]=1;
}
tot=0;
memset(first,-1,sizeof(first));
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(G[i][j]==0)
{
addedge(i,j);
addedge(j,i);
}
}
}
memset(DFN,0,sizeof(DFN));
memset(odd,0,sizeof(odd));
count=0;top=0;
for(int i=1;i<=n;i++)
{
if(!DFN[i])
dfs(i);
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(!odd[i])
ans++;
}
printf("%d\n",ans);
}
return 0;
}