UVaLive3523

发表于 | 分类于 |

题目传送门

Description

有$n(n\le 1000)$个骑士，$m(m\le1000000)$对骑士互相憎恨，要3个以上的骑士且保证互相憎恨的骑士不会坐在相邻位置才能开会议，求多少骑士一定不能参加任何一次会议。

多组测试数据。

Input

每组测试数据：

第一行：两个整数，$n$、$m$意义如题。

接下来$m$行：每行两个整数$k_1$和$k_2$，表示这两个骑士互相憎恨。

当$n$和$m$为0时文件输入结束。

Output

一个整数，一定不能参加的骑士的个数（原题样例有毒）。

Solution

在不互相憎恨的骑士间连一条边，能开会的骑士一定在一个简单奇圈上，而简单奇圈一定在双连通分量上，只要这个双连通分量不是二分图就行了。

问题就转化成找不在不是二分图的双连通分量上的点的个数。

Code

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string.h>
//#include<>
using namespace std;
struct EDGE
{
	int v;
	EDGE *next;
}edge[2100000],*ind[1100];
struct S
{
	int u,v;
}s[2100000];
int n,m,el=0,sl,sum;
bool map[1100][1100],ans[1100];
///
vector<int> bcc[1100];
int pre[1100],Time,bn,bccn[1100];
///
void input(int u,int v)
{
	edge[++el].v=v;
	edge[el].next=ind[u];
	ind[u]=&edge[el];
}
int dfs(int u,int fa)
{
	int lowu=pre[u]=++Time,child=0;
	for(EDGE *k=ind[u];k!=NULL;k=k->next)
	{
		int v=k->v;
		if(pre[v]==0)
		{
			s[++sl].v=v,s[sl].u=u;
			child++;
			int lowv=dfs(v,u);
			lowu=min(lowv,lowu);
			if(lowv>=pre[u])
			{
				bcc[++bn].clear();
				while(1)
				{
					int x=s[sl].u,y=s[sl].v;
					sl--;
					if(bccn[x]!=bn) { bcc[bn].push_back(x); bccn[x]=bn; }
					if(bccn[y]!=bn) { bcc[bn].push_back(y); bccn[y]=bn; }
					if(x==u&&y==v) break;
				}
			}
		}
		else if(pre[v]<pre[u] && v!=fa)
		{
			s[++sl].v=v,s[sl].u=u;
			lowu=min(lowu,pre[v]);
		}
	}
	return lowu;
}
void find_bcc()
{
	for(int i=1;i<=n;i++)
	{
		if(!pre[i]) dfs(i,-1);
	}
}
int color[1100];
bool color_che(int u,int c)
{
	for(EDGE *k=ind[u];k!=NULL;k=k->next)
	{
		int v=k->v;
		if(bccn[v]!=c) continue;
		if(color[v]==color[u]) return 0;
		if(!color[v])
		{
			color[v]=3-color[u];
			if(color_che(v,c)==0) return 0;
		}
	}
	return 1;
}
void che()
{
	for(int i=1;i<=bn;i++)
	{
		memset(color,0,sizeof(color));
		color[bcc[i][0]]=1;
		for(int j=0;j<bcc[i].size();j++) bccn[bcc[i][j]]=i;
		if(!color_che(bcc[i][0],i)) for(int j=0;j<bcc[i].size();j++) ans[bcc[i][j]]=1;
	}
}
void init()
{
	for(int i=0;i<=n;i++){
		ind[i]=NULL;
		pre[i]=ans[i]=bccn[i]=0;
	}
	bn=sl=Time=sum=el=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	init();
	while(n!=0&&m!=0)
	{
		for(int i=1;i<=m;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			map[x][y]=1;
			map[y][x]=1;
		}
		for(int i=1;i<n;i++)
			for(int j=i+1;j<=n;j++)
				if(!map[i][j]) input(i,j),input(j,i);
				else map[i][j]=0;
		find_bcc();
		che();
		for(int i=1;i<=n;i++) if(!ans[i]) sum++;
		printf("%d\n",sum);
		scanf("%d%d",&n,&m);
		init();
	}
	return 0;
}