黑白涂色问题

1. 问题描述

给定一个无向图, 给节点染色, 要求相邻节点不能相同颜色

2. 分析

直接 dfs 黑白染色就行

3. 代码

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;


void slove() {
    int n;
    cin >> n;

    vector<vector<int>> adj(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }

    vector<bool> vis(n, false);
    vector<int> col(n, -1);
    bool ans = true;

    function<void(int)> dfs = [&](int u)
    {
        vis[u] = true;
        for (auto & v : adj[u])
        {
            if (!vis[v])
            {
                col[v] = col[u] ^ 1;
                dfs(v);
            }

            if (col[u] == col[v])
            {
                ans = false;
            }
        }
    };

    for (int i = 0; i < n; i++)
    {
        if (!vis[i])
        {
            col[i] = 1;
            dfs(i);
        }
    }

    cout << (ans ? "YES" : "NO") << endl;
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        slove();
    }

    return 0;
}