Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4429 [BJOI2018]染色

Posted on Edited on In
Symbols count in article: 2.7k Reading time ≈ 2 mins.

结论题，靠手玩

染色

拿到题就先被吓了一跳，然后又看了看数据范围，毫无提示性

先盲猜一手考的二分图，也就是每个点的颜色集合都相同，然后……理所当然的 错了，但还是给了我们一点希望，因为我们发现明显，存在奇环就是No

那就还有不存在环和存在偶环两种情况

不存在环，即 $m < n$ ，考虑节点 $u$ 染为颜色 $A$ ，那么与它相连的节点 $v$ 最多只是有一个颜色不能染，此外便再无其它限制，明显是有染色方案的，故为Yes

再考虑偶环的情况，若只有一个偶环，即 $n = m$ ，我们将其断开，记断开处两个节点为根节点和尾节点，从根节点开始用无环的方法染色，设根节的颜色集合为 ${A, B}$ ，分三种情况：

  1. 若尾节点的颜色集合为 ${C, D}$ ，则染色成立
  2. 若尾节点的颜色集合为 ${A, C}$ ，只要根节点染为颜色 $B$ 即可
  3. 若尾节点的颜色集合为 ${A, B}$ ，设根节点染为颜色 $A$ 如果要让尾节点也必须染颜色 $A$ 则与尾节点相连的另一个点必须染为颜色 $B$ ，以此类推，每个节点的颜色都是“必须染成颜色 $X$ ”，设于根节点相连的另一个点的颜色是必须染成颜色 $E$ （这个 $E$ 可以等于于任何颜色，包括 $A, B$ ），由于这个“必须”，该节点的颜色集合一定是 ${A, E}$ （这样才能用“根节点染成颜色 $A$ ”推出“该节点染成颜色 $E$ ”），那么只要将根节点染成颜色 $B$ ，该节点染成颜色 $E$ ，由于刚才的一系列“必须”，尾节点只能保持颜色 $A$ 不变，染色成立

综上，若只有一个偶环，必定可以染色，故为Yes

那有多个偶环，即 $m > n$ ，怎么办？

先考虑两个偶环没有公共边，看看下图：

偶环

不难发现在这种构造下，最下方的点只能选颜色 $X$

于是有下图：

卡

明显为No

推广一下，考虑把节点 ${C, D}$ 拆成多个节点相连，换句话说，用多个节点连成的链作为广义的“交叉节点”，我们 玄学的 得出了结论：如果存在两个没有公共边但联通的环，那么答案是No，构造方法类似上图，可以证明（我也不知道咋证）这种情况的充分条件为 $m > n + 1$

最后只剩一种情况： $m = n + 1$ 且为偶环

这种情况下，要么有一个点度数为4，要么有两个点度数为3，度数为四的情况就和上图一样，明显为No

考虑两个度数为3的点，它们之间必定有3条路径，设路径长度（经过的边数）分别为 $(x, y, z)$ ，手玩一下 发现只有 $(2, 2, 2k), k\in \mathbb{N_+}$ 的情况为Yes

最后总结一下：

  1. $m < n$ 为Yes
  2. $m = n$ 且无奇环为Yes，否则为No
  3. $m = n + 1$ 且无奇环，若有两个度为3的节点且两点间路径为 $(2, 2, 2k), k\in \mathbb{N_+}$ 则为Yes，否则为No；若有奇环为No
  4. $m > n + 1$ 为No

注意以上结论均是在保证图联通的情况下得出

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
#include <bits/stdc++.h>
#define LL long long
#define VIT vector<int>::iterator
using namespace std;
const int N = 1e4 + 5;
int n, m, e, v;
int c[N], du[N];
bool f; //true-No,false-Yes
vector<int> to[N], cir;
void clear()
{
	for (int i = 1; i <= n; ++i)
		to[i].clear(), c[i] = 0;
	f = false;
}
void dfs(int x, int _c) //染色法判奇环
{
	if (f)
		return ;
	if (c[x])
	{
		if (c[x] != _c)
			f = true;
		return ;
	}
	c[x] = _c;
	++v;
	e += to[x].size();
	cir.push_back(x);
	for (VIT i = to[x].begin(); i != to[x].end(); ++i)
		dfs(*i, 3 - _c);
}
void topu() //拓扑处理非环节点
{
	queue<int> q;
	for (VIT i = cir.begin(); i != cir.end(); ++i)
	{
		du[*i] = to[*i].size();
		if (du[*i] == 1)
			q.push(*i);
	}
	int x;
	while (!q.empty())
	{
		x = q.front(), q.pop();
		for (VIT i = to[x].begin(); i != to[x].end(); ++i)
			if(--du[*i] == 1)
				q.push(*i);
	}
}
int main()
{
	int T, t, tt;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &n, &m);
		clear();
		for (int i = 1, x, y; i <= m; i++)
		{
			scanf("%d%d", &x, &y);
			to[x].push_back(y);
			to[y].push_back(x);
		}
		for (int i = 1; i <= n; ++i)
			if (!c[i])
			{
				e = v = 0;
				cir.clear();
				dfs(i, 1);
				e /= 2; //存的是双向边,真正的边数要除以2
				if (e > v + 1)
					f = true;
				if (f)
					break;
				if (e <= v)
					continue;
				topu();
				tt = 0;
				for (VIT j = cir.begin(); j != cir.end(); ++j)
					if (du[*j] == 2)
					{
						t = 0;
						for (VIT k = to[*j].begin(); k != to[*j].end(); ++k)
							if (du[*k] == 3)
								++t;
						if (t == 2)
							++tt;
					}
				if (tt < 2)
				{
					f = true;
					break;
				}
			}
		if (f)
			puts("NO");
		else
			puts("YES");
	}
	return 0;
}