思路：
对于该图，直接用建图貌似没法解，所以也很容易想到建补图，这样存在边的两个点就能再圆桌上做一起。也就将问题转化为对双连通分量中是否存在奇圈了。
我们将每次查询的边保存在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=0,stack[Maxm],top,odd[Maxn]; void init() { memset(index,-1,sizeof(index)); memset(vi,0,sizeof(vi)); memset(map,1,sizeof(map)); memset(col,0,sizeof(col)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(odd,0,sizeof(odd)); e=lab=top=0; } struct Edge{ int from,to,next,v; }edge[Maxm]; void addedge(int from, int to) { edge[e].v=0; edge[e].from=from; edge[e].to=to; edge[e].next=index[from]; index[from]=e++; edge[e].v=0; 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!=-1;i=edge[i].next) { temp=edge[i].to; if(vi[temp]) { if(col[temp]==-1) { col[temp]=!col[u]; if(find(temp))//寻找奇圈 return 1; } else if(col[temp]==col[u]) return 1; } } return 0; } int color(int u) { memset(col,-1,sizeof(col)); memset(vi,0,sizeof(vi)); col[u]=0; int i; do{//将该连通分量进行标记 i=stack[--top]; vi[edge[i].from]=1; vi[edge[i].to]=1; } while(edge[i].from!=u); if(find(u))//如果找到就进行标记 { for(i=1;i<=n;i++) { if(vi[i]) odd[i]=1; } } return 0; } int dfs(int u) { dfn[u]=low[u]=++lab; int i,j,temp; for(i=index[u];i!=-1;i=edge[i].next) { temp=edge[i].to; if(edge[i].v) continue;//一开始没加这个判断,一直WA edge[i].v=edge[i^1].v=1; 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 0; } int main() { int m,i,j,a,b; while(scanf("%d%d",&n,&m),n||m) { init(); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); map[a][b]=map[b][a]=0; } for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(map[i][j]) addedge(i,j); } } for(i=1;i<=n;i++) if(!dfn[i]) dfs(i); int ans=0; for(i=1;i<=n;i++) if(!odd[i]) ans++; printf("%d ",ans); } return 0; }