poj 2942 Knights of the Round Table bcc 交叉染色判定奇圈

缘起

图论好题~ poj 2942 Knights of the Round Table

求bcc在【1】中讲过. 这里用此题测一下板子.

本文参见的是解题报告 【2】（深度好文）

分析

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
亚瑟王要在圆桌上召开多场骑士会议，为了不引发骑士之间的冲突，并且能够让出席每场会议的议题有令人满意的结
果，每次开会前都必须对每场出席会议的骑士有如下要求：
1、  相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、  出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
 
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），
（注意, 为什么叫做所有会议? 因为亚瑟王可以组织多场会议开会.）
则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），
问亚瑟王至少要剔除多少个骑士才能顺利召开会议？
 
注意：
1、所给出的憎恨关系一定是双向的，不存在单向憎恨关系。
2、由于是圆桌会议，则每个出席的骑士身边必定刚好有2个骑士。即每个骑士的座位两边都必定各有一个骑士。
3、一个骑士无法开会，就是说至少有3个骑士才可能开会。

【输入】
多样例. 每个样例以一个n一个m开始
 1 ≤ n ≤ 1000 and 1 ≤ m ≤ 1000000
 然后是m行,每行2个正整数表示憎恨对. 输入以 0 0 结束

【输出】
答案

【样例输入】
5 5
1 4
1 5
2 5
3 4
4 5
0 0

【样例输出】
2

【限制】
7s

本题比较综合. 首先建立补图. 即如果A和B憎恨的话，则原图就有一条边A-B, 然后考虑补图. 则补图中有边表示两个人可以相邻. 则能参加一场圆桌会议的点必定是在补图中的一个环中的, 而能在一个环中的话, 一定构成点双（连通成环不就构成了一个点双么?你去掉任何一个点，剩下的点依旧是连通的）. 而亚瑟王希望能少开除骑士. 所以应该找bcc（极大xxx都是牛逼滴!）. 但是找到bcc就可以了吗? 显然不行! 因为我们不晓得bcc中是不是每个点都能出现在一个奇圈（即奇数个点构成的环）中. 所以我们查到了下面的数学定理

一个bcc中，如果存在奇圈P的话, 则所有点都能出现在某个奇圈Q(Q未必等于P)上，从而所有点都可以出席某场次的圆桌会议（场次未必一样）.

注意，此bcc包含元素个数未必>1（例如图中就2个互相连通的点, 则有两个bcc,每个bcc只包含1个点）,有可能等于1的.所以算法中收集到了一组bcc之后还要判断一下. 所以我们用tarjan得到一个bcc之后就要判断该bcc存不存在奇圈. 而我们还有

bcc存在奇圈的充要条件是它不是二分图.

所以我们用tarjan算法得到bcc之后，就要判断它是否是二分图. 而【3】中我们实现了使用交叉染色法判定一个无向连通图是否是二分图.

而反过来, 如果bcc不是二分图的话，则它不存在奇圈， 那么bcc中任何点都不可能出现在奇圈中，从而亚瑟王要将该bcc中所有的点都开除出去. 否则一旦某个点出现在某个奇圈中的话，则根据上面的定理就知道了任何点都会出现在某个奇圈中. 这就矛盾了. 所以本题的思路就清晰了

  1. 先使用tarjan算法求出所有的bcc
  2. 交叉染色法判定bcc是否是二分图. 如果不是的话（从而存在奇圈），则此bcc中所有的点都能参加会议（可能参与的会议场次不相同）. 如果是的话（从而不存在奇圈），则此bcc中的所有点都要被亚瑟王开除掉.

但是要注意哈~ 和【1】中的bcc由边构成不同，此处的bcc是由点构成的. 而且要把割点包含进去. 例如下图中的两个圈都是bcc——他们都包含割点3.

这是因为在【1】 中，bcc是由边构成的. 但是本题使用边刻画bcc不是太方便. 还是用点比较方便. 所以考虑到两个bcc有顶点公共（例如上图中的2个bcc共用3这个顶点）, 所以打算开一个布尔数组进行哈希. 防止重复算开除的点.

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
129
130
131
132
133
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
using namespace std;
//#define LOCAL

const int maxn = 1005;
int g[maxn][maxn],n,m,timestamp[maxn], low[maxn], t, bcc[maxn], top; // 本题构建补图,使用邻接矩阵较为方便, bcc[0,...,top-1]是当前收集得到的一组bcc
stack<int> s;
bool mark[maxn],v[maxn], color[maxn];

bool ddfs(int i)
{
	for (int j = 0; j<top; j++)
	{
		if (g[bcc[i]][bcc[j]])
		{
			if (!v[bcc[j]])
			{
				v[bcc[j]] = true,color[bcc[j]] = !color[bcc[i]];
				if (!ddfs(j))
				{
					return false; // 不是二分图
				}
			}
			else if (color[bcc[j]] == color[bcc[i]]) // 相邻者同色,则不是二分图
			{
				return false;
			}
		}
	}
	return true;
}

void handlerbcc(int cur, int i)
{
	top = 0; // 这里开始收集bcc, 其实完全可以设置一个bccnum以及一个vector<int> bcc[maxn]来收集全部bcc, 只是本题只需要遇到一组bcc就处理一组,所以不需要这么干
	bcc[top++] = cur; // 如文中配图所示, 割点(3)是一定要放进来的, 但是割点不能从s中弹栈出去.因为它也要进别的bcc中呢~
	int j;
	do 
	{
		j = s.top(), s.pop();
		bcc[top++] = j;
	} while (j!=i); // 成功收集一只bcc
	for (int i = 0; i<top; i++) // 开始在bcc上跑交叉染色法判定该bcc是否是二分图
	{
		color[bcc[i]] = v[bcc[i]] = false;
	}// 初始化
	color[bcc[0]] = v[bcc[0]] = true; // 交叉染色起点染色
	if (top>1 && !ddfs(0)) // 如果bcc数量>1 而且不是二分图的话,则该bcc中所有的点都能参见会议
	{
		for (int i = 0; i<top; i++)
		{
			mark[bcc[i]] = true;
		}
	}
}

void dfs(int cur, int fa)
{
	timestamp[cur] = low[cur] = ++t;
	s.push(cur);
	for (int i = 1; i<=n; i++)
	{
		if (g[cur][i])
		{
			if (!timestamp[i]) // 树边
			{
				dfs(i, cur);
				low[cur] = min(low[cur], low[i]);
				if (low[i]>=timestamp[cur]) // 出现割点cur或者根节点1, 注意, 本题不需要计算出哪些是割点,所以不需要【4】中的cut数组,而且就算根节点1不是割点, 也是要收割的
				{
					handlerbcc(cur, i); // 将原先tarjan求割点的板子中的cut[cur]=true换成了别的业务代码——handlerbcc
				}
			}
			else if (i!=fa) // 返祖边
			{
				low[cur] = min(low[cur], timestamp[i]);
			}
		}
	}
}

int main() {

#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(scanf("%d%d", &n,&m), n||m)
	{
		memset(timestamp, 0, sizeof(timestamp));
		memset(low, 0, sizeof(low));
		t  = 0;
		for (int i = 1; i<=n; i++)
		{
			for (int j = 1; j<=n;j++)
			{
				g[i][j] = i!=j;
			}
		} // 大部分是1,对角线为0
		while(m--)
		{
			int a,b;
			scanf("%d%d", &a, &b);
			g[a][b] = g[b][a] = 0;
		} // 得到补图g
		memset(mark, 0, sizeof(mark));
		for (int i = 1; i<=n; i++) // 注意, 补图g未必连通的! 所以要在不同的连通分支上求各个连通分支上的bcc
		{
			if (!timestamp[i])
			{
				t = 0; // 时间戳归0
				while(!s.empty())
				{
					s.pop();
				}
				dfs(i,0); // 从i作为根节点跑 tarjan 算法
			}
		}
		int ans = 0;
		for (int i = 1; i<=n;i++)
		{
			ans+=!mark[i];
		}
		printf("%d\n", ans);
	}
	return 0;
}

ac情况

Status Accepted
Time 1188ms
Memory 1608kB
Length 2529
Lang C++
Submitted 2019-09-09 15:27:31
Shared
RemoteRunId 20845599

参考

【1】https://yfsyfs.github.io/2019/05/24/%E6%97%A0%E5%90%91%E5%9B%BE%E7%9A%84%E7%82%B9%E5%8F%8C%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F-%E5%8F%88%E7%A7%B0%E5%9D%97/

【2】https://blog.csdn.net/lyy289065406/article/details/6756821

【3】https://yfsyfs.github.io/2019/08/21/%E7%89%9B%E5%AE%A2%E7%BD%91-%E4%BA%8C%E5%88%86%E5%9B%BE%E5%88%A4%E5%AE%9A%E4%B9%8B%E4%BA%A4%E5%8F%89%E6%9F%93%E8%89%B2%E6%B3%95/

【4】https://yfsyfs.github.io/2019/09/08/poj-1144-Network-%E5%89%B2%E7%82%B9/