【POJ 2942】Knights of the Round Table（双联通分量+染色判奇环）

【POJ 2942】Knights of the Round Table（双联通分量+染色判奇环）

Description

Input

Output

Sample Input

5 5
1 4
1 5
2 5
3 4
4 5
0 0

Sample Output

2

Hint

Source

题目大意：有n个骑士，m个仇视关系，每一个关系a b表示a与b老死不相往来，。

如今亚瑟王想要定期举办圆桌会议。圆桌会议要求到的骑士围成一圈。也就是每一个骑士一定会有左右两个相邻的骑士。要求相邻的骑士间不可有直接的仇视关系。

举行圆桌会议的骑士数目必须大于1。而且必须为奇数。

问须要剔除多少骑士才干正常举办会议。

有一个意思我没读出来，就是并不须要留下的骑士能參与同一场会议，会议能够举行多场，仅仅要留下的骑士能參与当中一场就可以。

这样建立补图，也就是骑士友好关系的图后。处于不同的双连通子图中的点一定无法出席同一场圆桌会议。由于这些点间要么是仇恨关系，要么仅仅有一条友好关系，无法成环。

这样范围就缩小到同一双连通分量中。

这里用到了一个结论，对于一个双连通分量，假设存在奇环，那么这个双连通分量中的每个点都一定会存在于至少一个奇环中。

由于不论什么一个点都有两条以上到这个奇环的路径，两条路径在连接奇环上的两个点，能够把奇环变为偶链和奇链 这样依据该点到这两个点间点个数的奇偶性进行选择 就保证一定能够构成奇环。

相同，假设不存在奇环，则全部双连通分量中的点都不存在于不论什么一个奇环中。

代码例如以下：

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8;

bool can[2333];
bool in[2333];
bool mp[2333][2333];
bool vis[2333];
int col[2333];
int dfn[2333],low[2333];
stack <int> s;
int n,tim;

bool cal(int u)
{
//	printf("%d\n",u);
	queue <int> q;
	q.push(u);
	memset(col,-1,sizeof(col));
	col[u] = 1;

	while(!q.empty())
	{
		u = q.front();
		q.pop();
		for(int i = 1; i <= n; ++i)
		{
			if(u != i && in[i] && !mp[u][i])
			{
	//			printf("%d->%d %d %d\n",u,i,col[u],col[i]);
				if(col[i] == -1)
				{
					col[i] = col[u]^1;
					q.push(i);
				}else if(col[i] == col[u]) return true;
			}
		}
	}
	return false;
}

void tarjan(int u,int pre)
{
	s.push(u);
	dfn[u] = low[u] = tim++;
	vis[u] = 1;
	for(int i = 1; i <= n; ++i)
	{
		if(i == u || i == pre || mp[u][i]) continue;
		if(!vis[i])
		{
			tarjan(i,u);
			low[u] = min(low[u],low[i]);
			if(low[i] >= dfn[u])
			{
				memset(in,0,sizeof(in));
				while(s.top() != i)
				{
					in[s.top()] = 1;
					s.pop();
				}
				in[i] = 1;
				s.pop();
				in[u] = 1;
				if(cal(u))
				{
					for(int i = 1; i <= n; ++i)
						if(in[i]) can[i] = 1; 
				}
			}
		}else low[u] = min(low[u],dfn[i]);
	}
}

int main()
{
	//fread();
	//fwrite();

	int m,u,v;
	while(~scanf("%d%d",&n,&m) && (n+m))
	{
		memset(mp,0,sizeof(mp));
		while(m--)
		{
			scanf("%d%d",&u,&v);
			mp[u][v] = mp[v][u] = 1;
		}

		memset(vis,0,sizeof(vis));
		memset(can,0,sizeof(can));
		tim = 0;
		for(int i = 1; i <= n; ++i)
			if(!vis[i]) tarjan(i,i);

		int ans = 0;
		for(int i = 1; i <= n; ++i)
			ans += can[i];

		printf("%d\n",n-ans);
	}

	return 0;
}