【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;

}