思路：
对于该图，直接用建图貌似没法解，所以也很容易想到建补图，这样存在边的两个点就能再圆桌上做一起。也就将问题转化为对双连通分量中是否存在奇圈了。
我们将每次查询的边保存在stack中，当遇到关键点的时候，stack里面保存的就是一个连通分量。在该连通分量中进行深搜，每次标记一个与父节点相反的颜色。当某次子节点与父节点颜色相同，那么就存在奇圈，且该连通分量中所有的点都在奇圈中。将这些点标记，最后进行遍历就行了。
引用discuss里的话：
一个块若无法做二分图染色，势必存在一个长度为奇数的环
任找一个奇环C，则对于任意一个非环上的点A，一定有两条不相交的路，连向这个奇环，交奇环于两个不同的点P、Q（否则这就不是一个双连通分量）
那么在环C上有两条P-->Q的路径，一条经过奇数条边，一条经过偶数条边
其中一条同PA、AQ相连后，一定是个奇环，所以A一定也在一个奇环上
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define Maxn 1010
#define Maxm Maxn*Maxn
using namespace std;
int index[Maxn],vi[Maxn],dfn[Maxn],col[Maxn],low[Maxn],map[Maxn][Maxn],e,n,lab=,stack[Maxm],top,odd[Maxn];
void init()
{
memset(index,-,sizeof(index));
memset(vi,,sizeof(vi));
memset(map,,sizeof(map));
memset(col,,sizeof(col));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(odd,,sizeof(odd));
e=lab=top=;
}
struct Edge{
int from,to,next,v;
}edge[Maxm];
void addedge(int from, int to)
{
edge[e].v=;
edge[e].from=from;
edge[e].to=to;
edge[e].next=index[from];
index[from]=e++;
edge[e].v=;
edge[e].to=from;
edge[e].from=to;
edge[e].next=index[to];
index[to]=e++;
}
int find(int u)
{
int i,j,temp;
for(i=index[u];i!=-;i=edge[i].next)
{
temp=edge[i].to;
if(vi[temp])
{
if(col[temp]==-)
{
col[temp]=!col[u];
if(find(temp))//寻找奇圈
return ;
}
else
if(col[temp]==col[u]) return ;
}
}
return ;
}
int color(int u)
{
memset(col,-,sizeof(col));
memset(vi,,sizeof(vi));
col[u]=;
int i;
do{//将该连通分量进行标记
i=stack[--top];
vi[edge[i].from]=;
vi[edge[i].to]=;
}
while(edge[i].from!=u);
if(find(u))//如果找到就进行标记
{
for(i=;i<=n;i++)
{
if(vi[i])
odd[i]=;
}
}
return ;
}
int dfs(int u)
{
dfn[u]=low[u]=++lab;
int i,j,temp;
for(i=index[u];i!=-;i=edge[i].next)
{
temp=edge[i].to;
if(edge[i].v) continue;//一开始没加这个判断,一直WA
edge[i].v=edge[i^].v=;
stack[top++]=i;
if(!dfn[temp])
{
dfs(temp);
if(low[temp]>=dfn[u]) color(u);
low[u]=min(low[u],low[temp]);
}
low[u]=min(low[u],dfn[temp]);
}
return ;
}
int main()
{
int m,i,j,a,b;
while(scanf("%d%d",&n,&m),n||m)
{
init();
for(i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
map[a][b]=map[b][a]=;
}
for(i=;i<=n;i++)
{
for(j=i+;j<=n;j++)
{
if(map[i][j])
addedge(i,j);
}
}
for(i=;i<=n;i++)
if(!dfn[i])
dfs(i);
int ans=;
for(i=;i<=n;i++)
if(!odd[i])
ans++;
printf("%d\n",ans);
}
return ;
}