P11022 「LAOI-6」Yet Another Graph Coloration Problem

P11022 「LAOI-6」Yet Another Graph Coloration Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

关于无解情况，如果这个图有两块连通块，那么不可能同时有黑色白色，假设 \(1,2\) 连通块，设 \(1\) 中有黑色，因为 \(2\) 中点不能到 \(1\)，所以 \(2\) 中只能是黑色，又因为 \(2\) 中都是黑色，\(1\) 中点不能到 \(2\)，所以 \(1\) 中点都是黑色，所以一个图全是黑色。 所以只能是一整块连通图。

先考虑贪心，先把所有点变成白色，看看那些点能变为黑色。

容易发现，对于一个无出边的环，可以随便选黑色，但如果有出边，即有桥的话，桥相连点只能是同色，可以发现只要有环，那么就可以选出来两种颜色，即一定有解。而如果这张图没有环，即是一个树，那么两点不可能存在多个简单路径，因此无解。

所以，我们可以先给桥边点标记。然后从点 1 开始染黑色，并把和点 1 相连的，非同一双连通分量（即环）里的桥点也染成黑色即可。

此题结束。

注意，对于大测试量，不要循环 memset 容易爆，要采用循环清空。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 200010, M = N * 2;

int h[N], ne[M], e[M], idx;
int n, m;
int dfn[N], timestamp, dcc_cnt, low[N];
int stk[N], top, id[N];
bool st[N], flag1;
bool B[N];
vector<int> g[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u, int from)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u;
    
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j, i);
            low[u] = min(low[u], low[j]);
            
            if (dfn[u] < low[j])
            {
                st[u] = st[j] = true;
            }
        }
        else if (i != (from ^ 1))
        {
            low[u] = min(low[u], dfn[j]);
        }
    }
    
    if (dfn[u] == low[u])
    {
        int y;
        dcc_cnt ++ ;
        
        do {
            y = stk[top -- ];
            id[y] = dcc_cnt;
            g[dcc_cnt].push_back(y);
        }while (y != u);
        if (g[dcc_cnt].size() >= 3) flag1 = true; // 说明有环
    }
}

void dfs(int u)
{
    B[u] = 1;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (st[j] && id[u] != id[j] && !B[j])
            dfs(j);
    }
}

int main()
{   
    int T;
    cin >> T;
    
    while (T -- )
    {
        cin >> n >> m;
        
        for (int i = 1; i <= n; i ++ )
        {
            st[i] = 0;
            dfn[i] = 0;
            h[i] = -1;
            top = 0;
            g[i].clear();
            B[i] = 0;
        }
        
        idx = dcc_cnt = 0;
        flag1 = 0;
        timestamp = 0;
        
        while (m -- )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            add(a, b);
            add(b, a);
        }
        
        int cnt = 0;
        for (int i = 1; i <= n; i ++ )
            if (!dfn[i])
            {
                tarjan(i, -1);
                cnt ++ ;   
            }
            
        if (cnt > 1)
        {
            puts("-1");
            continue;
        }
        
        if (flag1) 
        {
            dfs(1);
            for (int i = 1; i <= n; i ++ )
            {
                if (B[i]) putchar('B');
                else putchar('W');
            }
        }
        else 
        {
            puts("-1");
            continue;
        }
        puts("");
    }
    
    return 0;
    
}