P7178 解题报告

· · 题解

简述题意

给定一张 |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;
}