圆桌会议必须满足：奇数个人参与，相邻的不能是敌人（敌人关系是无向边）。
求无论如何都不能参加会议的骑士个数。只需求哪些骑士是可以参加的。
我们求原图的补图：只要不是敌人的两个人就连边。
在补图的一个奇圈里（由奇数个点组成的环）每个点都是可以参加的。而一个奇圈一定在点双连通分量里，所以我们把原图的每个点双连通分量找出来，然后判断是否有奇圈。用到了几个引理：
非二分图至少有一个奇圈。
点双连通分量如果有奇圈，那么每个点都在某个奇圈里（不一定是同一个）。
于是问题转化为对每个点双连通分量，判断它是不是二分图，如果不是，那就把它里面所有点都标记为可行，最后用总数减去可行的就是答案（无论如何都不能参加会议的骑士个数）。
二分图染色就是dfs，对一个点染色后，对其相邻点染上与自己不同的颜色，如果相邻点已经染过，就判断其颜色是否和自己相同，是则说明不是二分图，否则跳过该相邻点。直到全部染完。
#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("%d ",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; }