题意
有n个骑士经常举行圆桌会议，商讨大事。每次圆桌会议至少应有3个骑士参加，且相互憎恨的骑士不能坐在圆桌旁的相邻位置。如果发生意见分歧，则需要举手表决，因此参加会议的骑士数目必须是奇数，以防赞同和反对票一样多。知道哪些骑士相互憎恨之后，你的任务是统计有多少个骑士不可能参加任何一个会议。
分析
建模：以骑士为结点建立无向图G。如果两个骑士可以相邻，那么就在他们之间连一条无向边，则题目转化为，求并不在任何一个奇圈上的点的个数。如果图G不连通，应对每个连通分量分别求解。
我们首先要找出图中所有的双连通分量（因为简单圈上所有的结点必属于一个双连通分量），然后判断每个连通分量是否含有奇圈。我们知道二分图不存在奇圈，所以我们对每个双连通分量进行二分染色进行判断就可以。
这里还有一个很重要的结论：如果结点v所属的某个双连通分量B不是二分图，那么v一定属于一个奇圈。训练指南上有这个证明
主算法：对于每个连通分量的双连通分量B，若他不是二分图，给B中的所有结点标记为“在奇圈上”。注意，由于每个割顶属于多个双连通分量，他可能会被标记多次，需要特殊处理一下。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector> using namespace std;
const int maxn=+;
const int maxm=+;
int vis[maxn][maxn];
int n,m,sz;
int head[maxn],to[maxm],Next[maxm];
struct Edge{
int u,v;
};
void add_edge(int a,int b){
++sz;
to[sz]=b;Next[sz]=head[a];head[a]=sz;
}
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
vector<int>bcc[maxn];
stack<Edge>S;
int dfs(int u,int fa){
int lowu=pre[u]=++dfs_clock;
int child=;
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
Edge e=(Edge){u,v};
if(!pre[v]){
S.push(e);
child++;
int lowv=dfs(v,u);
lowu=min(lowu,lowv);
if(lowv>=pre[u]){
iscut[u]=;
bcc_cnt++;bcc[bcc_cnt].clear();
for(;;){
Edge x=S.top();S.pop();
if(bccno[x.u]!=bcc_cnt){
bcc[bcc_cnt].push_back(x.u);
bccno[x.u]=bcc_cnt;
}
if(bccno[x.v]!=bcc_cnt){
bcc[bcc_cnt].push_back(x.v);
bccno[x.v]=bcc_cnt;
}
if(x.u==u&&x.v==v)break;
}
}
}
else if(pre[v]<pre[u]&&v!=fa){
S.push(e);
lowu=min(lowu,pre[v]);
}
}
if(fa<&&child==)iscut[u]=;
return lowu;
}
void find_bcc(int n){
memset(pre,,sizeof(pre));
memset(iscut,,sizeof(iscut));
memset(bccno,,sizeof(bccno));
dfs_clock=bcc_cnt=;
for(int i=;i<=n;i++)
if(!pre[i])dfs(i,-);
}
int color[maxn];
bool bipartite(int u,int num){
for(int i=head[u];i!=-;i=Next[i]){
int v=to[i];
if(bccno[v]!=num)continue;
if(color[v]==color[u])return false;
if(!color[v]){
color[v]=-color[u];
if(!bipartite(v,num))return false;
}
}
return true;
}
int ANS[maxn]; int main(){
//freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
memset(vis,,sizeof(vis));
int a,b;
for(int i=;i<=m;i++){
scanf("%d%d",&a,&b);
vis[a][b]=vis[b][a]=;
}
sz=-;
memset(head,-,sizeof(head));
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
if(i==j)continue;
if(!vis[i][j]){
add_edge(i,j);
vis[i][j]=;
}
if(!vis[j][i]){
add_edge(j,i);
vis[j][i]=;
}
}
}
/*for(int i=1;i<=n;i++){
printf("%d :",i);
for(int j=head[i];j!=-1;j=Next[j]){
int v=to[j];
printf("%d ",v);
}
printf("\n");
}*/ find_bcc(n);
/* for(int i=1;i<=n;i++){
printf("%d %d\n",i,bccno[i]);
}
cout<<bcc_cnt<<endl;*/ memset(ANS,,sizeof(ANS));
for(int i=;i<=bcc_cnt;i++){
for(int j=;j<bcc[i].size();j++){
if(iscut[bcc[i][j]]){
bccno[bcc[i][j]]=i;
}
}
memset(color,,sizeof(color));
color[bcc[i][]]=;
if(!bipartite(bcc[i][],i)){
for(int j=;j<bcc[i].size();j++){
int u=bcc[i][j];
ANS[u]=;
}
}
}
int ans=;
for(int i=;i<=n;i++)
if(ANS[i])
ans++;
ans=n-ans;
printf("%d\n",ans);
}
return ;
}