首页 > 代码库 > POJ 2942 Knights of the Round Table 黑白着色+点双连通分量

POJ 2942 Knights of the Round Table 黑白着色+点双连通分量

题目来源:POJ 2942 Knights of the Round Table

题意:统计多个个骑士不能參加随意一场会议 每场会议必须至少三个人 排成一个圈 而且相邻的人不能有矛盾 题目给出若干个条件表示2个人直接有矛盾

思路:求补图  能够坐在一起 就是能够相邻的人建一条边 然后假设在一个奇圈上的都是满足的 那些不再不论什么一个奇圈的就是不满足 求出全部奇圈上的点 总数减去它就是答案

首先有2个定理 

1.一个点双连通分量是二分图 你就没有奇圈 假设有奇圈  那就不是二分图  充分必要条件 所以

2.一个点双连通分量有奇圈  那这个点双连通分量全部点都在奇圈上

所以这题就求点双连通分量 然后对每一个分量进行二分图判定 不是二分图 就把该双连通分量全部点都标记  标记是由于一个割点可能属于多个双连通分量

所以标记在求和

#include <vector>
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
const int maxn = 1010;
struct Edge
{
	int u, v;
	Edge(){}
	Edge(int u, int v): u(u), v(v){}
};
vector <int> a[maxn];
vector <int> bcc[maxn];
int pre[maxn];
int low[maxn];
int bccno[maxn];
int dfs_clock;
int bcc_cnt;
int bri;
int n, m;
int degree[maxn];
stack <int> S;
int A[maxn][maxn];
int odd[maxn];
int color[maxn];
bool bipartite(int u, int b)
{
	for(int i = 0; i < a[u].size(); i++)
	{
		int v = a[u][i];
		if(bccno[v] != b)
			continue;
		if(color[u] == color[v])
			return false;
		if(!color[v])
		{
			color[v] = 3 - color[u];
			if(!bipartite(v, b))
				return false;
		}
	}
	return true;
}
void dfs(int u, int fa)
{
	low[u] = pre[u] = ++dfs_clock;
	S.push(u);
	for(int i = 0; i < a[u].size(); i++)
	{
		int v = a[u][i];
		if(v == fa)
			continue;
		if(!pre[v])
		{
			dfs(v, u);
			low[u] = min(low[u], low[v]);
			if(pre[u] <= low[v])
			{
				bcc_cnt++;
				while(1)
				{
					int x = S.top(); S.pop();
					bccno[x] = bcc_cnt;
					bcc[bcc_cnt].push_back(x);
					if(x == v)
					{
						bcc[bcc_cnt].push_back(u);
						break;
					}
				}
			}
		}
		else if(v != fa)
			low[u] = min(low[u], pre[v]);
	}
	/*if(low[u] == pre[u])
	{
		bcc_cnt++;
		while(1)
		{
			int x = S.top(); S.pop();
			bccno[x] = bcc_cnt;
			bcc[bcc_cnt].push_back(x);
			if(x == u)
				break;
		}
	}*/
}
void find_bcc()
{
	memset(pre, 0, sizeof(pre));
	memset(bccno, 0, sizeof(bccno));
	dfs_clock = bcc_cnt = bri = 0;
	for(int i = 1; i <= n; i++)
		if(!pre[i])
			dfs(i, -1);
}
int main()
{
	
	while(scanf("%d %d", &n, &m) && (n||m))
	{
		memset(A, 0, sizeof(A));
		while(m--)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			A[u][v] = A[v][u] = 1;
		}
		for(int i = 0; i <= n; i++)
		{
			a[i].clear();
			bcc[i].clear();
		}
		for(int i = 1; i <= n; i++)
			for(int j = i+1; j <= n; j++)
			{
				if(A[i][j])
					continue;
				a[i].push_back(j);
				a[j].push_back(i);
			}
		find_bcc();
		memset(odd, 0, sizeof(odd));
		for(int i = 1; i <= bcc_cnt; i++)
		{
			memset(color, 0, sizeof(color));
			for(int j = 0; j < bcc[i].size(); j++)
				bccno[bcc[i][j]] = i;
			int u = bcc[i][0];
			color[u] = 1;
			if(!bipartite(u, i))
			{
				for(int j = 0; j < bcc[i].size(); j++)
					odd[bcc[i][j]] = 1;
			}
		}
		int ans = n;
		for(int i = 1; i <= n; i++)
			if(odd[i])
				ans--;
		printf("%d\n", ans);
	}
	return 0;
}


POJ 2942 Knights of the Round Table 黑白着色+点双连通分量