https://vjudge.net/problem/UVALive-3523
题意：
有n个骑士经常举行圆桌会议，商讨大事。每次圆桌会议至少应有3个骑士参加，且相互憎恨的骑士不能坐在圆桌旁的相邻位置。如果发生意见分歧，则需要举手表决，因此参加会议的骑士数目必须是奇数。
统计有多少个骑士不可能参加任何一个会议。
思路：
把不相互憎恨的骑士之间连一条无向边。
因为是圆桌，所以骑士之间要构成一个环，相当于是一个点双连通分量的模型。
环的点的个数得是奇数，这就需要用到前面二分图染色的知识，如果是偶数，则是二分图。
不能参加任何会议的骑士就是不在任何奇圈中的。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
using namespace std; const int maxn=+; struct Edge
{
int u,v;
Edge(int x,int y):u(x),v(y){}
};
stack<Edge> S; int n,m;
int A[maxn][maxn];
int color[maxn];
int odd[maxn];
int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt;
vector<int> G[maxn],bcc[maxn]; //二分图染色
bool bipartite(int u,int b)
{
for(int i=;i<G[u].size();i++)
{
int v=G[u][i];
if(bccno[v]!=b) continue;
if(color[v]==color[u]) return false;
if(!color[v])
{
color[v]=-color[u];
if(!bipartite(v,b)) return false;
}
}
return true;
} int dfs(int u,int fa)
{
int lowu=pre[u]=++dfs_clock;
int child=;
for(int i=;i<G[u].size();i++)
{
int v=G[u][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]=true;
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(,-);
} int main()
{
//freopen("D:\\input.txt","r",stdin);
while(~scanf("%d%d",&n,&m) && n)
{
for(int i=;i<n;i++) G[i].clear();
memset(A,,sizeof(A));
while(m--)
{
int u,v;
scanf("%d%d",&u,&v);
u--;
v--;
A[u][v]=A[v][u]=;
}
for(int i=;i<n;i++)
{
for(int j=i+;j<n;j++)
{
if(!A[i][j]) {G[i].push_back(j);G[j].push_back(i);}
}
}
find_bcc(n);
memset(odd,,sizeof(odd));
for(int i=;i<=bcc_cnt;i++)
{
memset(color,,sizeof(color));
for(int j=;j<bcc[i].size();j++) bccno[bcc[i][j]]=i; //给同一个连通分量的点加上同一个编号
int u=bcc[i][];
color[u]=;
if(!bipartite(u,i)) //如果是奇圈，给连通分量里的点做上标记
{
for(int j=;j<bcc[i].size();j++) odd[bcc[i][j]]=;
}
}
int ans=n;
for(int i=;i<n;i++)
if(odd[i]) ans--;
printf("%d\n",ans);
}
return ;
}