题目链接：http://vjudge.net/contest/141787#problem/A
http://poj.org/problem?id=2942
此题很经典
知识点：DFS染色，点-双连通
题意：
亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议？
能够坐在一起的人，连一条边，题目就是求所有的点中，有多少个点不在任何一个奇圈里。
这个无向图，求出每个点双连通分量，但是不是每个点双连通分量都是奇圈，如果它是偶圈，那么就可以用 dfs 染色，这样我们把每个点连通分量染色，要是染色失败，那么这些点都可以构成奇圈，也就是说这些点都OK。最后查一遍这些点。
有了之前的 无向图的割顶，桥，点-双连通分量，DFS染色，就好写好多了！！！
#include <bits/stdc++.h> #include <stdio.h> #include <stack> #include <algorithm> #include <string.h> #include <vector> using namespace std; const int Maxn = 1000 +10; int A[Maxn][Maxn]; int pre[Maxn<<1]; bool iscut[Maxn]; int bccno[Maxn]; int dfs_clock; int bcc_cnt; vector <int> G[Maxn],bcc[Maxn]; struct Edge { int u,v; Edge(int u=0,int v=0) : u(u),v(v) {} }; stack <Edge> 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(lowu, lowv); 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].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); } int odd[Maxn], color[Maxn]; 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 main() { int n, m; while(scanf("%d%d", &n, &m) == 2 && n) { for(int i = 0; i < n; i++) G[i].clear(); memset(A, 0, sizeof(A)); for(int i = 0; i < m; i++) { int u, v; 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; }