题意：多个骑士要开会，3人及以上才能凑一桌，其中部分人已经互相讨厌，肯定不坐在同一桌的相邻位置，而且一桌只能奇数个人才能开台。给出多个人的互相讨厌图，要求多少人开不成会（注：会议不要求同时进行，一个人开多个会不冲突）？
分析：
给的是互相讨厌的图，那么转成互相喜欢的吧，扫一遍，如果不互相讨厌就认为互相喜欢，矩阵转邻接表先。
有边相连的两个点代表能坐在一块。那么找出一个圈圈出来，在该圈内的点有奇数个人的话肯定能凑成1桌。圈圈？那就是简单环了，跟点双连通分量的定义好像一样：每个点都能同时处于1个及以上的简单环中。这么说，只要有环，他们就能凑一桌了（每个环开一桌，同1人参加多桌并不冲突）。
但是奇数的问题怎么解决？如果是一个点双连通分量是个偶图（即二分图），那么肯定只有偶数环。想想，图都双连通了，那么必有简单环，1个简单环中如果是奇数个了，着色法染色时必定有冲突。那么就用偶图判定来解决这个问题。
实现：
（1）互相讨厌图转互相喜欢图。
（2）求点双连通分量，并把同个点双连通分量内的点都给归类出来。（注意可能图不连通）
（3）黑白着色判定偶图，非偶图的留下，偶图忽略。3个人一下的点双连通分量也忽略。
（4）只要1个点能够处于任一非偶图中，标记其为“可以开会”。
（5）统计哪些人开不了会。（肯定是那些3人以下的，偶数个人还想坐一块的）
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#define LL long long
#define pii pair<int,int>
using namespace std;
const int N=+;
const int INF=0x7f7f7f7f;
int n, m, bcc_cnt, dfn_clock; //点双连通分量的个数
int g[N][N], dfn[N], low[N], bcc_no[N], col[N], flag[N]; stack<pair<int,int> > stac;
vector<int> bcc[N], vect[N]; void DFS(int x,int far)
{
dfn[x]=low[x]=++dfn_clock;
for(int i=; i<vect[x].size(); i++)
{
int t=vect[x][i];
if(!dfn[t])
{
stac.push(make_pair(x,t));
DFS(t,x);
low[x]=min(low[x],low[t]);
if(low[t]>=dfn[x])
{
bcc[++bcc_cnt].clear();
while()
{
int a=stac.top().first;
int b=stac.top().second;
stac.pop();
if(bcc_no[a]!=bcc_cnt)
{
bcc_no[a]=bcc_cnt;
bcc[bcc_cnt].push_back(a);
}
if(bcc_no[b]!=bcc_cnt)
{
bcc_no[b]=bcc_cnt;
bcc[bcc_cnt].push_back(b);
}
if(a==x && b==t) break;
}
}
}
else if(dfn[t]<dfn[x] && t!=far) //特别注意，“dfn[t]<dfn[x]”这句是必须的，特别是在求点双连通分量时。否则可能乱。
{
stac.push(make_pair(x,t));
low[x]=min(low[x],dfn[t]);
}
}
} void find_bcc() //找出点双连通分量，放在bcc中
{
bcc_cnt= dfn_clock= ;
memset(low, ,sizeof(low));
memset(bcc_no,,sizeof(bcc_no));
memset(dfn, ,sizeof(dfn));
for(int i=; i<=n; i++)
if(!dfn[i]) DFS(i,-);
} int color(int num) //判断是否偶图,偶图不含奇圈
{
col[bcc[num][]]=;
deque<int> que;que.push_back(bcc[num][]);
while(!que.empty()) //广搜着色
{
int x=que.front();que.pop_front();
for(int i=; i<bcc[num].size(); i++)
{
int t=bcc[num][i];
if(x!=t&&!g[x][t]) //只要有边
{
if(col[t]==col[x]) return false; //颜色已经相同，非偶图
if(!col[t]) //无染过才进
{
col[t]=-col[x];
que.push_back(t);
} }
}
}
return true;
} int color_it()
{
memset(flag, , sizeof(flag));
for(int i=; i<=bcc_cnt; i++)
{
memset(col, , sizeof(col)); //每次都要置0，因为可能有点属于两个双连通分量
if(bcc[i].size()<) continue; //不够人数开会
if(color(i)==false) //不是偶图
for(int j=; j<bcc[i].size(); j++) //这些人都可以开会，mark一下
flag[bcc[i][j]]=;
} int cnt=;
for(int i=; i<=n; i++) //统计哪些人不能开会
if(!flag[i]) cnt++;
return cnt;
} int main()
{
freopen("input.txt", "r", stdin);
int a, b;
while(scanf("%d%d",&n,&m), n+m)
{
for(int i=; i<=n; i++) vect[i].clear();
memset(g,,sizeof(g)); for(int i=; i<m; i++)
{
scanf("%d%d",&a,&b);
g[a][b]=g[b][a]=;
}
for(int i=; i<=n; i++) //转邻接表
for(int j=i+; j<=n; j++)
if(!g[i][j]) vect[i].push_back(j),vect[j].push_back(i); find_bcc();
printf("%d\n",color_it()); } return ;
}
AC代码