题目链接：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 = +; int A[Maxn][Maxn]; int pre[Maxn<<];
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=,int v=) : u(u),v(v) {}
}; stack <Edge> S; int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = ;
for(int i = ; 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 < && child == ) iscut[u] = ;
return lowu;
} void find_bcc(int n)
{
memset(pre, , sizeof(pre));
memset(iscut, , sizeof(iscut));
memset(bccno, , sizeof(bccno));
dfs_clock = bcc_cnt = ;
for(int i = ; i < n; i++)
if(!pre[i]) dfs(i, -);
} int odd[Maxn], color[Maxn];
bool bipartite(int u, int b)
{
for(int i = ; 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] = - color[u];
if(!bipartite(v, b)) return false;
}
}
return true;
} int main()
{
int n, m;
while(scanf("%d%d", &n, &m) == && n)
{
for(int i = ; i < n; i++) G[i].clear(); memset(A, , sizeof(A));
for(int i = ; i < m; i++)
{
int u, v;
scanf("%d%d", &u, &v);
u--;
v--;
A[u][v] = A[v][u] = ;
}
for(int u = ; u < n; u++)
for(int v = u+; v < n; v++)
if(!A[u][v])
{
G[u].push_back(v);
G[v].push_back(u);
} find_bcc(n); memset(odd, , sizeof(odd));
for(int i = ; i <= bcc_cnt; i++)
{
memset(color, , sizeof(color));
for(int j = ; j < bcc[i].size(); j++)
bccno[bcc[i][j]] = i;
int u = bcc[i][];
color[u] = ;
if(!bipartite(u, i))
{
for(int j = ; j < bcc[i].size(); j++)
odd[bcc[i][j]] = ;
}
}
int ans = n;
for(int i = ; i < n; i++)
if(odd[i])
ans--;
printf("%d\n", ans);
}
return ;
}