题目大意：有n个骑士经常举行圆桌会议，每次圆桌会议至少要有3个骑士参加(且每次参加的骑士数量是奇数个)，且所有互相憎恨的骑士不能坐在圆桌旁的相邻位置，问有多少个骑士不可能参加任何一个会议

解题思路：以骑士为点建立无向图G。如果两个骑士可以相邻(即他们并不互相憎恨)，即可连一条边。
则题目就转化为求不在任何一个简单奇圈上的结点个数
首先，圈就是一个双连通的分量，所以第一件事就是将所有的双连通分量求出来，接着再判定这个双连通分量是不是奇圈
奇圈的判定就是用二分图染色判定，如果某个圈能被二分图染色，那么这个圈必然不是奇圈，因为二分图染色，染色的点是成对的，所以点的数量是偶数的

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; #define N 1010 struct Edge{ int u, v; Edge() {} Edge(int u, int v): u(u), v(v) {} }; int pre[N], iscut[N], bccno[N], dfs_clock, bcc_cnt; int odd[N], color[N]; vector
         
           G[N], bcc[N]; stack
          
            S; int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0; for (int i = 0; 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(lowv, lowu); if (lowv >= pre[u]) { iscut[u] = true; bcc_cnt++; bcc[bcc_cnt].clear(); while (1) { 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 < 0 && child == 1) iscut[u] = 0; return lowu; } void find_bcc(int n) { memset(pre, 0, sizeof(pre)); memset(iscut, 0, sizeof(iscut)); memset(bccno, 0, sizeof(bccno)); dfs_clock = bcc_cnt = 0; for (int i = 0; i < n; i++) if (!pre[i]) dfs(i, -1); } bool bipartite(int u, int b) { for (int i = 0; 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] = 3 - color[u]; if (!bipartite(v, b)) return false; } } return true; } int A[N][N]; int main() { int cas = 1, n, m; while (scanf(%d%d, &n, &m) != EOF && n + m) { for (int i = 0; i < n; i++) G[i].clear(); memset(A, 0, sizeof(A)); int u, v; for (int i = 0; i < m; i++) { scanf(%d%d, &u, &v); u--; v--; A[u][v] = A[v][u] = 1; } for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++) if (!A[u][v]) { G[u].push_back(v); G[v].push_back(u); } find_bcc(n); memset(odd, 0, sizeof(odd)); for (int i = 1; i <= bcc_cnt; i++) { memset(color, 0, sizeof(color)); for (int j = 0; j < bcc[i].size(); j++) bccno[bcc[i][j]] = i; int u = bcc[i][0]; color[u] = 1; if (!bipartite(u, i)) for (int j = 0; j < bcc[i].size(); j++) { odd[bcc[i][j]] = 1; } } int ans = n; for (int i = 0; i < n; i++) if(odd[i]) ans--; printf(%d , ans); } return 0; } 
          
         
        
       
      
     
    
   

?