题目大意：
有N个骑士，他们要开圆桌会议，也就是要坐成一个圈，相互憎恨的两个骑士是不能坐在相邻位置的，那样他们就会打起来。给出所有的憎恨关系。如果有人不可能开会，例如他可能憎恨所有人，就不能再去开会了。求这样人的个数。
解题思路：
1、首先根据题目给出的憎恨关系建图，然后求补图，这个图表示哪个骑士可以和哪个骑士坐在一起。
2、在图中求出圈，也就是双联通分量，这可以用到Tarjan算法的思想，通过Tarjan算法执行过程中退栈求出一个又一个双联通分量。
3、对于双联通分量我们需要在其中找到一个奇圈，这需要一个利用了DFS的交叉染色法，在代码中我建补图的时候没有建立自己和自己的边，当用这个方法找出来的奇圈这少有三个点在圈上。
4、对于在奇圈上的标记出来，最后计数一共有多少，就知道不能开会的有多少了
下面是代码：
#include <stdio.h>
#include <string.h>
struct node
{
int to,next;
} list1[1005*1000],stack1[1005*1000];
bool map1[1005][1005],vis[1005],ist[1005];
int time,top,head[1005],cnt,n,m,dfn[1005],low[1005];
void init()
{
memset(map1,0,sizeof(map1));
memset(vis,0,sizeof(vis));
memset(ist,0,sizeof(ist));
time=1;
top=0;
cnt=0;
}
int min(int a,int b)
{
if(a>b)a=b;
return a;
}
void Build()
{
int i,j,x,y;
for(i=0; i<m; i++)
{
scanf("%d%d",&x,&y);
x--;
y--;
map1[x][y]=true;
map1[y][x]=true;
}
for(i=0; i<n; i++)
{
for(j=0; j<n; j++)
{
map1[i][j]=!map1[i][j];
}
map1[i][i]=false;
}
for(i=0; i<n; i++)
{
head[i]=-1;
for(j=0; j<n; j++)
{
if(map1[i][j])
{
list1[cnt].to=j;
list1[cnt].next=head[i];
head[i]=cnt;
cnt++;
}
}
}
}
bool does(int u,int c,int *col,bool *vist)
{
col[u]=c;
for(int i=head[u];i!=-1;i=list1[i].next)
{
if(vist[list1[i].to])
{
if(col[list1[i].to]==c)
{
return true;
}
else if(!col[list1[i].to]&&does(list1[i].to,3-c,col,vist))
{
return true;
}
}
}
return 0;
}
void isnt(int u,int v)
{
bool vist[1005]={false};
int col[1005]={0};
while(top>0)
{
top--;
vist[stack1[top].next]=1;
vist[stack1[top].to]=1;
if(stack1[top].next==u&&stack1[top].to==v)
{
break;
}
}
if(does(u,1,col,vist))
{
for(int i=0;i<n;i++)
{
if(vist[i])
{
ist[i]=true;
}
}
}
}
void dfs(int u,int up)
{
dfn[u]=time;
low[u]=time;
time++;
vis[u]=true;
for(int i=head[u]; i!=-1; i=list1[i].next)
{
if(map1[u][list1[i].to])
{
map1[u][list1[i].to]=false;
map1[list1[i].to][u]=false;
stack1[top].next=u;
stack1[top].to=list1[i].to;
top++;
if(!vis[list1[i].to])
{
dfs(list1[i].to,u);
low[u]=min(low[u],low[list1[i].to]);
if(low[list1[i].to]>=dfn[u])
{
isnt(u,list1[i].to);
}
}
else if(list1[i].to!=up)
{
low[u] = min(low[u], dfn[list1[i].to]);
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m),n+m)
{
int i;
init();
Build();
for(i=0; i<n; i++)
{
dfs(i,0);
}
int sum=0;
for(i=0;i<n;i++)
{
if(ist[i])sum++;
}
printf("%d\n",n-sum);
}
return 0;
}