题解：P11022 「LAOI-6」Yet Another Graph Coloration Problem

pigeonteam · 2024-09-08 08:34:52 · 题解

前置

我们假设这张图最开始全部是白色的。

分析

首先，我们很容易就可以得出，一个不联通的图一定不存在合法的染色方案。至于为什么可以自己想一想。
因为一定会存在两个点不同色且不在一个连通块中，不然就是全部点都是一个颜色。

其次，我们不难发现，在一个无向图上要有两条不同的简单路径到同一个点，那这个点就一定会在一个环上。

然后，我们从环上任取一个点染黑，发现从这个点出去的不经过在这个环上的点的点仍然可能和这个点只有一条简单路径。并且别的点由于环的存在一定有两条简单路径通向这些点。所以我们把我们选择的点能不经过环上的点直接通向的点也染成黑色的。
然后这道题就做完了。

其余提示

本题有多测，记得清空。

下面是部分代码。

#define maxn 200005

int t, n, m, u, v;
vector<int> g[maxn];
// 存图
bool color[maxn], vis[maxn], in[maxn], sizvis[maxn];
// color:目前的颜色 vis:在染色过程中是否被访问过
// in:是否在选中的环上 sizvis:在搜索连通块大小是是否被访问过
vector<int> lst;
// lst:表示在环上的数有哪些
int p;
// 记录dfs染色时环到哪里截止

inline int siz(int x)
{
    int ans = 1;
    sizvis[x] = 1;
    for (auto i : g[x])
    {
        if (!sizvis[i])
            ans += siz(i);
    }
    return ans;
}

inline bool dfs(int x, int fa)
{
    if (vis[x])
    {
        p = x;
        in[x] = 1;
        return true;
    }
    vis[x] = 1;
    for (auto i : g[x])
    {
        if (i == fa)
            continue;
        if (dfs(i, x))
        {
            in[x] = 1;
            lst.push_back(x);
            break;
        }
    }
    return x == p ? 0 : in[x];
}

inline void paint(int id) // 染色
{
    color[id] = 1;
    for (auto i : g[id])
    {
        if (color[i] || in[i])
            continue;
        paint(i);
    }
}

inline void init() // 初始化
{
    lst.clear();
    p = 0;
    for (int i = 1; i <= n; ++i)
    {
        g[i].clear();
        color[i] = 0;
        vis[i] = 0;
        in[i] = 0;
        sizvis[i] = 0;
    }
}

int main()
{
    FastIO::read(t);
    while (t--)
    {
        init();
        FastIO::read(n, m);
        for (int i = 1; i < n; ++i)
            g[i].clear();
        for (int i = 0; i < m; ++i)
        {
            FastIO::read(u, v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int sizee = siz(1);
        if (sizee != n) // 不是联通图
        {
            puts("-1");
            continue;
        }
        dfs(1, 0);
        if (lst.empty()) // 没有环
        {
            puts("-1");
            continue;
        }
        paint(lst.front());
        for (int i = 1; i <= n; ++i)
            putchar(color[i] ? 'B' : 'W');
        putchar('\n');
    }
    return 0;
}