原题大意

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

算法分析

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

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
const int maxn = 1e3+5;

int color[maxn], odd[maxn];
int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;
vector<int> G[maxn], bcc[maxn];
int A[maxn][maxn];
struct Edge{
    int u, v;
    Edge(int _u, int _v){
        u = _u;
        v = _v;
    }
};

stack<Edge> S;

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 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();
                for(;;){
                    Edge x = S.top(); S.pop();
                    if(bccno[x.u] != bcc_cnt){
                        bcc[bcc_cnt].pb(x.u);
                        bccno[x.u] = bcc_cnt;
                    }
                    if(bccno[x.v] != bcc_cnt){
                        bcc[bcc_cnt].pb(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){
    mem(pre,0);mem(iscut,0);mem(bccno,0);
    dfs_clock = bcc_cnt = 0;
    for(int i = 1; i <= n; i++){
        if(!pre[i]) dfs(i,-1);
    }
}
int main(){
  //  freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    while(cin >> n >> m){
        if(!n && !m) break;
        for(int i = 0; i <= n; i++) G[i].clear();

        mem(A,0);
        for(int i = 0; i < m; i++){
            int u, v;
            cin >> u >> v;
            A[u][v] = A[v][u] = 1;
        }

        for(int u = 1; u <= n; u++){
            for(int v = u+1; v <= n; v++)
                if(!A[u][v]) G[u].pb(v),G[v].pb(u);

        }
        find_bcc(n);
        mem(odd, 0);
        for(int i = 1; i <= bcc_cnt; i++){
            mem(color,0);
            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 = 1; i <= n; i++) if(odd[i]) ans--;
        cout << ans << "\n";
    }
    return 0;
}