[COCI 2014/2015 #4] SABOR

厚着脸皮安利一下我的博客。

题意

给定一张 $n$ 个点的无向图，每个点的度数不超过 $5$，要求对每个点染色（黑或白），使得每个点不能有超过 $2$ 个同色点与其相邻。

思路

本题点的度数和要求十分特别，思路也很有意思。

考虑先让每个点都染成黑色，如果与当前点 $x$ 相邻的点中，同色点的数量超过 $2$，那么异色点的数量一定不超过 $2$（每个点的度数不超过 $5$），此时将点 $x$ 的颜色翻转即可。不过将点 $x$ 的颜色翻转后，现在与点 $x$ 同色的点有可能不合法，此时把这些点当作点 $x$ 重新操作即可。

时间复杂度爆炸？非也。设一个边为特别的边当且仅当该边两端的点同色。初始时，特别的边最多有 $\frac{5n}{2}$ 条。每次操作，至少会使特别的边减少一条，最多减少 $\frac{5n}{2}$ 次，故时间复杂度为 $O(n)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n;
vector<int> a[N];
bool color[N]; 
void solve(int x)
{
	int cnt=0;
	for(int i=0;i<a[x].size();i++)
		if(color[a[x][i]]==color[x]) cnt++;
	if(cnt>2)
	{
		color[x]^=1;
		for(int i=0;i<a[x].size();i++)
			if(color[a[x][i]]==color[x]) solve(a[x][i]);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=5;i++)
	{
		int p;
		scanf("%d",&p);
		while(p--)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			a[x].push_back(y);
			a[y].push_back(x);
		}
	}
	for(int i=1;i<=n;i++)
		solve(i);
	for(int i=1;i<=n;i++)
		if(color[i]) putchar('A');
		else putchar('B');
	return 0;
}