【点双+二分图判定】Knights of the Round Table

图论

传送门：POJ2942

题意：

国王要在圆桌上召开骑士会议，但是若干对骑士之间互相憎恨。

① 相互憎恨的两个骑士不能坐在相邻的2个位置；

② 出席会议的骑士数必须是奇数。

求无法出席任何会议的骑士的个数 。

思路：

建补图+求点双连通分量，根据某引理：如果一个点双连通分量中存在一个奇环，则该点双中的每个点都可出现在奇环中。

然后染色判断一下就好。

注意： 求点双不是边双，由于一个点可能在多个点双中，所以枚举的点不能直接出锅；

出锅代码：

1
2
for (;stack[top+1]!=v;){belong[stack[top]]=cnt; top--;}
belong[u]=cnt;

注意for条件不能换为stack[top]!=u

因为u,v中间可能存在很多未出锅的点

详见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 1200
#define M 3000000
int n,m,x,y,tot,clock,top,cnt,sum,ss;
int head[N],dfn[N],low[N],belong[N],p[N][N],col[N],stack[N],q[N],ff[N];
struct edge{int v,nxt;}e[M];
void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void init(){
	clock=top=cnt=0; tot=1;
	memset(head,0,sizeof head); memset(e,0,sizeof e);
	memset(dfn,0,sizeof dfn); memset(low,0,sizeof low);
	memset(p,0,sizeof p); memset(col,-1,sizeof col);
	memset(ff,0,sizeof ff); memset(belong,0,sizeof belong);
}
void solve(int i){
	int tt=0,ww=1; q[1]=i; col[i]=1; bool flag=0;
	while (tt<ww){
		int u=q[++tt],color=col[u];
		for (int j=head[u];j;j=e[j].nxt){
			int v=e[j].v;
			if (belong[v]!=belong[u]) continue;
			if (col[v]==color){flag=1; break;}
			else if (col[v]==-1){col[v]=1^color; q[++ww]=v;}
		}
		if (flag) break;
	}
	if (flag)
		for (int j=1;j<=n;j++)
			if (belong[j]==belong[i]) ff[j]=1;
}
void tarjan(int u,int fa){
	dfn[u]=low[u]=++clock; stack[++top]=u;
	for (int i=head[u];i;i=e[i].nxt){
		if (i==(fa^1)) continue;
		int v=e[i].v;
		if (!dfn[v]){
			tarjan(v,i); low[u]=min(low[u],low[v]);
			if (low[v]>=dfn[u]){
				cnt++;
				for (;stack[top+1]!=v;){belong[stack[top]]=cnt; top--;}
				//出栈条件很重要，和边双不同 
				belong[u]=cnt;
				memset(col,-1,sizeof col); solve(u);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
int main(){
	while (1){
		scanf("%d%d",&n,&m);
		if (n==0 && m==0) break;
		init();
		for (int i=1;i<=m;i++){scanf("%d%d",&x,&y); p[x][y]=p[y][x]=1;}
		for (int i=1;i<=n;i++)
			for (int j=i+1;j<=n;j++)
				if (!p[i][j]){add(i,j); add(j,i);}
		for (int i=1;i<=n;i++)
		 if (!dfn[i]) tarjan(i,0);
		sum=0; for (int i=1;i<=n;i++) if (!ff[i] || !head[i]) sum++;
		printf("%d\n",sum);
	}
	
	return 0;
}