圆桌骑士（双连通分量，二分染色，奇圈）

## 题目描述 有n个骑士经常举行圆桌会议，商讨大事。每次圆桌会议至少有3个骑士参加，且相互憎恨的骑士不能坐在圆桌的相邻位置。如果发生意见分歧，则需要举手表决，因此参加会议的骑士数目必须是大于1的奇数，以防止赞同和反对票一样多。知道那些骑士相互憎恨之后，你的任务是统计有多少骑士不可能参加任何一个会议。 ### Input Data 包含多组数据，每组数据格式如下： 第一行为两个整数n和m（1<=n<=1000, 1<=m<=10^6）。 以下m行每行包含两个整数k1和k2(1<=k1,k2<=n），表示骑士k1和k2相互憎恨。 输入结束标记为n=m=0 ### Output Data 对于每组数据，在一行中输出一个整数，即无法参加任何会议的骑士个数。 ### Input sample 5 5 1 4 1 5 2 5 3 4 4 5 0 0 ### Output sample 2 ------------ ------------ ------------ ## 题解部分 本题利用二分图+双连通分量解决。首先，可以把所有相互之间不憎恨的骑士连接一条无向边，那么题目转化为在这个无向图中有多少个结点不在任何一个简单奇圈上。这里的“简单奇圈”指的是圈上顶点个数为奇数，且每个结点只会出现在一个圈中。简单圈上的点一定属于同一个双连通分量，因此需要事先找到所有的双连通分量，而二分图中是没有奇圈的，因此我们只需要关注那些不是二分图的双连通分量即可。 但是不是所有双连通分量上的点都在奇圈上呢？答案是肯定的，证明如下 假设u1,u2所在一个奇圈C上，那么必然存在2条从u1到u2的路径，而且长度为一奇一偶，如果新添加一个结点v,它的一条边连接u1,另一条边连接u2，可以发现，u1经过v到达u2的路径长度为偶数，加上原来存在的那个长度为奇数的路径，恰好构成一个新的奇圈。由此证明了所有点都在奇圈上。 所以只用求出所有点双连通分量，再判断这些点双连通分量是否为二分图，不为二分图的就是奇圈。那么这些连通分量上的点，也就是骑士都能参加会议，最后输出n减去能参加会议的骑士数量。 ```cpp #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; struct Stuck { int u,v; }s[10000]; int n,m,cnt=0,tot=0,num=0,p=0; int head[200010],nxt[200010],to[200010]; int low[1010],pre[1010],f[1010]; int no[1010][1010],odd[1010],col[1010]; vector <int> vec[1000]; void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void dfs(int u,int fa)//tarjan求点连通分量 { low[u]=pre[u]=++tot; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(!pre[v]) { s[++p].u=u,s[p].v=v; dfs(v,u); low[u]=min(low[u],low[v]); if(low[v]>=pre[u]) { num++; vec[num].clear(); while(p) { if(f[s[p].u]!=num) vec[num].push_back(s[p].u),f[s[p].u]=num; if(f[s[p].v]!=num) vec[num].push_back(s[p].v),f[s[p].v]=num; if(s[p].u==u && s[p].v==v) break; p--; } p--; } } else if(pre[v]<pre[u] && v!=fa) { s[++p].u=u,s[p].v=v; low[u]=min(low[u],pre[v]); } } } int half(int u,int k)//二分图染色，判断是否为二分图 { for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(f[v]!=k) continue; if(col[v]==col[u]) return 0; if(!col[v]) { col[v]=3-col[u]; if(!half(v,k)) return 0; } } return 1; } int main() { while(1) { memset(f,0,sizeof(f)); memset(no,0,sizeof(no)); memset(pre,0,sizeof(pre)); memset(low,0,sizeof(low)); memset(odd,0,sizeof(odd)); memset(head,-1,sizeof(head)); cnt=0,tot=0,num=0,p=0; scanf("%d%d",&n,&m); if(!n && !m) break; for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); if(!x && !y) break; no[x][y]=1; no[y][x]=1; }//建立原图的补图，将可以在一起的骑士连边 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j || no[i][j]) continue; addedge(i,j); } for(int i=1;i<=n;i++) if(!pre[i]) dfs(i,0); for(int i=1;i<=num;i++) { memset(col,0,sizeof(col)); for(int j=0;j<vec[i].size();j++) f[vec[i][j]]=i; col[vec[i][0]]=1; if(!half(vec[i][0],i)) {//若不为二分图则都打上标记 for(int j=0;j<vec[i].size();j++) odd[vec[i][j]]=1; } } int ans=n; for(int i=1;i<=n;i++) if(odd[i]) ans--; cout<<ans<<endl; } return 0; } ```