圆桌会议必须满足：奇数个人参与，相邻的不能是敌人（敌人关系是无向边）。
求无论如何都不能参加会议的骑士个数。只需求哪些骑士是可以参加的。
我们求原图的补图：只要不是敌人的两个人就连边。
在补图的一个奇圈里（由奇数个点组成的环）每个点都是可以参加的。而一个奇圈一定在点双连通分量里，所以我们把原图的每个点双连通分量找出来，然后判断是否有奇圈。用到了几个引理：
非二分图至少有一个奇圈。 点双连通分量如果有奇圈，那么每个点都在某个奇圈里（不一定是同一个）。
于是问题转化为对每个点双连通分量，判断它是不是二分图，如果不是，那就把它里面所有点都标记为可行，最后用总数减去可行的就是答案（无论如何都不能参加会议的骑士个数）。
二分图染色就是dfs，对一个点染色后，对其相邻点染上与自己不同的颜色，如果相邻点已经染过，就判断其颜色是否和自己相同，是则说明不是二分图，否则跳过该相邻点。直到全部染完。
代码语言：javascript复制#include<cstdio>
#include<cstring>
const int N = 1010;
const int M = 2000010;
struct Edge
{
int to,next;
}edge[M];
int head[N],tot;
int Low[N],DFN[N],Stack[N],Belong[N];
int Index,top;
int block;//点双连通分量的个数
bool Instack[N];
bool can[N];
bool ok[N];//标记
int tmp[N];//暂时存储双连通分量中的点
int cc;//tmp的计数
int color[N];//染色
void addedge(int u,int v)
{
edge[tot].to = v;edge[tot].next = head[u];head[u] = tot ;
}
bool dfs(int u,int col)//染色判断二分图
{
color[u] = col;
for(int i = head[u];~i;i = edge[i].next)
{
int v = edge[i].to;
if( !ok[v] )continue;
if(~color[v])
{
if(color[v]==col)return false;
continue;
}
if(!dfs(v,!col))return false;
}
return true;
}
void Tarjan(int u,int pre)
{
int v;
Low[u] = DFN[u] = Index;
Stack[top ] = u;
Instack[u] = true;
for(int i = head[u];~i;i = edge[i].next)
{
v = edge[i].to;
if(v == pre)continue;
if( !DFN[v] )
{
Tarjan(v,u);
if(Low[u] > Low[v])Low[u] = Low[v];
if( Low[v] >= DFN[u])
{
block ;
int vn;
cc = 0;
memset(ok,false,sizeof ok);
do
{
vn = Stack[--top];
Belong[vn] = block;
Instack[vn] = false;
ok[vn] = true;
tmp[cc ] = vn;
}
while( vn!=v );
ok[u] = 1;
memset(color,-1,sizeof(color));
if( !dfs(u,0) )
{
can[u] = true;
while(cc--)can[tmp[cc]]=true;
}
}
}
else if(Instack[v] && Low[u] > DFN[v])
Low[u] = DFN[v];
}
}
void solve(int n)
{
memset(DFN,0,sizeof DFN);
memset(Instack,false,sizeof Instack);
Index = block = top = 0;
memset(can,false,sizeof can);
for(int i = 1;i <= n;i )
if(!DFN[i])
Tarjan(i,-1);
int ans = n;
for(int i = 1;i <= n;i )
if(can[i])
ans--;
printf("%dn",ans);
}
void init()
{
tot = 0;
memset(head,-1,sizeof head);
}
int g[N][N];
int main()
{
int n,m,u,v;
while(scanf("%d%d",&n,&m),n)
{
init();
memset(g,0,sizeof g);
while(m--)
{
scanf("%d%d",&u,&v);
g[u][v]=g[v][u]=1;
}
for(int i = 1;i <= n;i )
for(int j = 1;j <= n;j )
if(i != j && g[i][j]==0)
addedge(i,j);
solve(n);
}
return 0;
}
