「POJ2942」 Knights of the Round Table（二分图 交叉染色+ 点双连通分量）
题干：
亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议？
题解：
这道题在建边方面还有所讲究。若我们就只是将相互憎恨的士兵连边，后续维护方面十分困难。若我们将不相互憎恨的士兵连边，答案其实就是最大的拥有奇数个节点的环，也就是奇环（因为只有不相互憎恨的士兵才可以坐在一起，我们这样建边就是说谁和谁可以坐在一起）。
又因为这道题主要是点的问题（去掉多少个骑士，也就是节点），不难想到点双连通分量。
同样是 tarjan 寻找割点（为了找到环），每找到一个割点，就判断一下是否是二分图（奇环一定有奇数个节点，一定不是二分图）。
如果是二分图，那就标记掉这个环上的所有点，因为它一定不成立。
Code：
1 #include<cstdio>
2 #include<cstring>
3 #include<vector>
4 #define $ 1111
5 using namespace std;
6 int m,n,first[$],tot,tar,dfn[$],low[$],sta[$],up,ans,col[$];
7 bool vis[$][$],judge[$],whe[$];
8 struct tree{ int to,next; }a[$*2000];
9 inline int min(int x,int y){ return x<y?x:y; }
10 inline void add(int x,int y){
11 a[++tot]=(tree){ y,first[x] };
12 first[x]=tot;
13 }
14 inline void init(){
15 memset(first,0,sizeof(first));
16 memset(a,0,sizeof(a));
17 memset(dfn,0,sizeof(dfn));
18 memset(low,0,sizeof(low));
19 memset(vis,0,sizeof(vis));
20 memset(sta,0,sizeof(sta));
21 memset(judge,0,sizeof(judge));
22 ans=tar=tot=up=0;
23 }
24 inline bool dfs(int x,int opt){
25 whe[x]=0; col[x]=opt;
26 for(register int i=first[x];i;i=a[i].next){
27 int to=a[i].to;
28 if(col[to]!=-1&&col[to]==opt) return 0;
29 if(whe[to]==1&&dfs(to,opt^1)==0) return 0;
30 }
31 return 1;
32 }
33 inline void tarjan(int x,int tmp=0){
34 dfn[x]=low[x]=++tar;
35 sta[++up]=x;
36 for(register int i=first[x];i;i=a[i].next){
37 int to=a[i].to;
38 if(!dfn[to]){
39 tarjan(to);
40 low[x]=min(low[x],low[to]);
41 if(low[to]>=dfn[x]){
42 std::vector<int> out;
43 memset(col,-1,sizeof(col));
44 memset(whe,0,sizeof(whe));
45 do{
46 tmp=sta[up--];
47 whe[tmp]=1;
48 out.push_back(tmp);
49 }while(tmp!=to);
50 whe[x]=1; out.push_back(x);
51 if(dfs(x,0)==0)
52 for(register int j=0;j<out.size();++j) judge[out[j]]=1;
53 }
54 }
55 else low[x]=min(low[x],dfn[to]);
56 }
57 }
58 inline void work(){
59 for(register int i=1,x,y;i<=m;++i)
60 scanf("%d%d",&x,&y), vis[x][y]=vis[y][x]=1;
61 for(register int i=1;i<=n;++i)
62 for(register int j=1;j<=n;++j)
63 if(i!=j&&!vis[i][j]) add(i,j);
64 for(register int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
65 for(register int i=1;i<=n;++i) if(judge[i]) ans++;
66 printf("%d
",n-ans);
67 }
68 signed main(){
69 while(~scanf("%d%d",&n,&m)){
70 if(m+n==0) return 0;
71 init(); work();
72 }
73 }