题意
有n个骑士经常举行圆桌会议，商讨大事。每次圆桌会议至少应有3个骑士参加，且相互憎恨的骑士不能坐在圆桌旁的相邻位置。如果发生意见分歧，则需要举手表决，因此参加会议的骑士数目必须是奇数，以防赞同和反对票一样多。知道哪些骑士相互憎恨之后，你的任务是统计有多少个骑士不可能参加任何一个会议。
分析
建模：以骑士为结点建立无向图G。如果两个骑士可以相邻，那么就在他们之间连一条无向边，则题目转化为，求并不在任何一个奇圈上的点的个数。如果图G不连通，应对每个连通分量分别求解。
我们首先要找出图中所有的双连通分量（因为简单圈上所有的结点必属于一个双连通分量），然后判断每个连通分量是否含有奇圈。我们知道二分图不存在奇圈，所以我们对每个双连通分量进行二分染色进行判断就可以。
这里还有一个很重要的结论：如果结点v所属的某个双连通分量B不是二分图，那么v一定属于一个奇圈。训练指南上有这个证明
主算法：对于每个连通分量的双连通分量B，若他不是二分图，给B中的所有结点标记为“在奇圈上”。注意，由于每个割顶属于多个双连通分量，他可能会被标记多次，需要特殊处理一下。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <stack> 6 #include <vector> 7 8 using namespace std; 9 const int maxn=1000+10; 10 const int maxm=2000000+10; 11 int vis[maxn][maxn]; 12 int n,m,sz; 13 int head[maxn],to[maxm],Next[maxm]; 14 struct Edge{ 15 int u,v; 16 }; 17 void add_edge(int a,int b){ 18 ++sz; 19 to[sz]=b;Next[sz]=head[a];head[a]=sz; 20 } 21 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt; 22 vector<int>bcc[maxn]; 23 stack<Edge>S; 24 int dfs(int u,int fa){ 25 int lowu=pre[u]=++dfs_clock; 26 int child=0; 27 for(int i=head[u];i!=-1;i=Next[i]){ 28 int v=to[i]; 29 Edge e=(Edge){u,v}; 30 if(!pre[v]){ 31 S.push(e); 32 child++; 33 int lowv=dfs(v,u); 34 lowu=min(lowu,lowv); 35 if(lowv>=pre[u]){ 36 iscut[u]=1; 37 bcc_cnt++;bcc[bcc_cnt].clear(); 38 for(;;){ 39 Edge x=S.top();S.pop(); 40 if(bccno[x.u]!=bcc_cnt){ 41 bcc[bcc_cnt].push_back(x.u); 42 bccno[x.u]=bcc_cnt; 43 } 44 if(bccno[x.v]!=bcc_cnt){ 45 bcc[bcc_cnt].push_back(x.v); 46 bccno[x.v]=bcc_cnt; 47 } 48 if(x.u==u&&x.v==v)break; 49 } 50 } 51 } 52 else if(pre[v]<pre[u]&&v!=fa){ 53 S.push(e); 54 lowu=min(lowu,pre[v]); 55 } 56 } 57 if(fa<0&&child==1)iscut[u]=0; 58 return lowu; 59 } 60 void find_bcc(int n){ 61 memset(pre,0,sizeof(pre)); 62 memset(iscut,0,sizeof(iscut)); 63 memset(bccno,0,sizeof(bccno)); 64 dfs_clock=bcc_cnt=0; 65 for(int i=1;i<=n;i++) 66 if(!pre[i])dfs(i,-1); 67 } 68 int color[maxn]; 69 bool bipartite(int u,int num){ 70 for(int i=head[u];i!=-1;i=Next[i]){ 71 int v=to[i]; 72 if(bccno[v]!=num)continue; 73 if(color[v]==color[u])return false; 74 if(!color[v]){ 75 color[v]=3-color[u]; 76 if(!bipartite(v,num))return false; 77 } 78 } 79 return true; 80 } 81 int ANS[maxn]; 82 83 int main(){ 84 //freopen("out.txt","w",stdout); 85 while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){ 86 memset(vis,0,sizeof(vis)); 87 int a,b; 88 for(int i=1;i<=m;i++){ 89 scanf("%d%d",&a,&b); 90 vis[a][b]=vis[b][a]=1; 91 } 92 sz=-1; 93 memset(head,-1,sizeof(head)); 94 for(int i=1;i<=n;i++){ 95 for(int j=1;j<=n;j++){ 96 if(i==j)continue; 97 if(!vis[i][j]){ 98 add_edge(i,j); 99 vis[i][j]=1; 100 } 101 if(!vis[j][i]){ 102 add_edge(j,i); 103 vis[j][i]=1; 104 } 105 } 106 } 107 /*for(int i=1;i<=n;i++){ 108 printf("%d :",i); 109 for(int j=head[i];j!=-1;j=Next[j]){ 110 int v=to[j]; 111 printf("%d ",v); 112 } 113 printf(" "); 114 }*/ 115 116 find_bcc(n); 117 /* for(int i=1;i<=n;i++){ 118 printf("%d %d ",i,bccno[i]); 119 } 120 cout<<bcc_cnt<<endl;*/ 121 122 memset(ANS,0,sizeof(ANS)); 123 for(int i=1;i<=bcc_cnt;i++){ 124 for(int j=0;j<bcc[i].size();j++){ 125 if(iscut[bcc[i][j]]){ 126 bccno[bcc[i][j]]=i; 127 } 128 } 129 memset(color,0,sizeof(color)); 130 color[bcc[i][0]]=1; 131 if(!bipartite(bcc[i][0],i)){ 132 for(int j=0;j<bcc[i].size();j++){ 133 int u=bcc[i][j]; 134 ANS[u]=1; 135 } 136 } 137 } 138 int ans=0; 139 for(int i=1;i<=n;i++) 140 if(ANS[i]) 141 ans++; 142 ans=n-ans; 143 printf("%d ",ans); 144 } 145 return 0; 146 }