自动搬运

查看原文

来自洛谷，原作者为

	elbissoPtImaerD Just keep it Quiet, it'll be all right. :-)

搬运于2025-08-24 22:27:23，当前版本为作者最后更新于2023-01-26 21:36:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简述题意

给定一张 $|V|=n$ 的图，以及若干条边。

满足每个点的度数 $d_i\le 5$。

你需要将这张图黑白染色，满足每一个点有不多于 $2$ 个同色点与其相邻。

解题报告

考虑：让所有点均同色，然后逐步调整出符合题意的构造。

对于某一个点 $u$，因为 $d_u\le 5$，如果它有超过 $2$ 个同色点，那么其必有不不超过 $2$ 个异色点。
此时将点 $u$ 变为异色就能让 $u$ 符合题意。

但是这样与 $u$ 相邻的点有可能不符合题意。

考虑将这些点作为新的 $u$ 做上述变色操作。
这样看似复杂度爆炸，实际上复杂度是有保证的。

我们定义一条边为不合法的当且仅当这条边的两个端点同色。
这样在初始时我们最多有 $\frac{5n}{2}$ 条不合法的边。
而每一次变色后，不合法的边的数量最劣也会减少 $1$。 故变色操作至多进行 $\frac{5n}{2}$ 次。

复杂度 $\mathcal{O(n)}$。

$\mathcal{Code:}$

const int N=2e5+3;
int n,cnt[N];
std::vector<int>G[N];
bool ans[N];
il void Upd(int u)
{
	ans[u]^=1;
	for(re int v:G[u])
		ans[u]^ans[v]?--cnt[u],--cnt[v]:(++cnt[u],++cnt[v]);
	for(re int v:G[u]) cnt[v]>2&&(Upd(v),7);
	return;
}
void Solve()
{
	rd(n);
	for(re int i=1,x,u,v;i<=5;++i)
		for(rd(x);x--;) rd(u),rd(v),G[u].pb(v),G[v].pb(u),++cnt[u],++cnt[v];
	for(re int i=1;i<=n;++i) cnt[i]>2&&(Upd(i),7);
	for(re int i=1;i<=n;++i) putchar(ans[i]?'A':'B');
	return;
}