#小红的基环树染色构造#

F-小红的基环树染色构造_牛客周赛 Round 126

该问题要求在一个基环树（Unicyclic Graph）上进行3-染色（3-Coloring）。基环树的拓扑结构可以严格定义为：一个核心环（Cycle）+ 若干挂在环上节点的树（Trees）。

• 核心约束：任意相邻节点颜色不同。
• 可用资源：3种颜色（红、黄、蓝）。
• 解的存在性：题目保证必然存在解。根据图论原理，任何简单图只要不是完全图 及其特例，并且最大度数与色数满足一定关系，通常容易染色。对于基环树：
  • 树部分：这是二分图，仅需2种颜色即可完成染色。
  • 环部分：偶环需要2色，奇环需要3色。
  • 结论：由于提供了3种颜色，即使环是奇数长度，也能完美覆盖。

拓扑分解与分步处理

解决基环树问题的最优架构通常采用环树分离策略。我们不应将图视为一个整体进行复杂的搜索，而应将其分解为两个独立的子问题：

1. 环的处理：解决闭环结构的冲突。
2. 树的处理：解决层级结构的传播。

算法

DFS 找环 + 贪心染色 + 树的遍历

相比于拓扑排序（剥洋葱法），直接使用 DFS（深度优先搜索） 处理此问题更为直观且易于实现状态的传递。

1. 第一阶段（寻环）：通过 DFS 找到图中的那条“回边（Back Edge）”，从而锁定环上的所有节点。
2. 第二阶段（环染色）：优先对环上的节点进行染色。由于环上的节点同时受前后两个邻居限制，属于“高约束”区域，必须优先满足。
3. 第三阶段（树染色）：以环上的节点为“根”，向外延伸的树进行染色。这部分约束极低（只受父节点限制），可直接贪心。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 0: 未访问, 1: 访问中(在栈里), 2: 已完全访问
    vector<int> vis(n + 1, 0);
    vector<int> parent(n + 1, -1);
    vector<int> cycle;
    vector<bool> onCycle(n + 1, false);
    bool found = false;
    auto dfs_cycle = [&](auto&& self, int u, int p) -> void {
        vis[u] = 1;
        parent[u] = p;

        for (int v : g[u]) {
            if (v == p)
                continue;
            if (vis[v] == 1) {
                if (!found) {
                    found = true;
                    int cur = u;
                    while (cur != v) {
                        cycle.push_back(cur);
                        onCycle[cur] = true;
                        cur = parent[cur];
                    }
                    cycle.push_back(v);
                    onCycle[v] = true;
                }
            } else if (vis[v] == 0) {
                self(self, v, u);
            }
        }

        vis[u] = 2;
    };
    dfs_cycle(dfs_cycle, 1, -1);

    vector<int> color(n + 1, 0);
    int m = cycle.size();
    for (int i = 0; i < m; i++) {
        if (i % 2 == 0) {
            if (m % 2 == 1 && i == m - 1)
                color[cycle[i]] = 3;
            else
                color[cycle[i]] = 1;
        } else if (i % 2 == 1) {
            color[cycle[i]] = 2;
        }
    }

    auto dfs_color = [&](auto&& self, int u, int p) -> void {
        for (int v : g[u]) {
            if (v == p || onCycle[v])
                continue;
            if (color[u] == 1)
                color[v] = 2;
            else
                color[v] = 1;
            self(self, v, u);
        }
    };
    for (int i = 1; i <= n; i++) {
        if (onCycle[i])
            dfs_color(dfs_color, i, -1);
    }

    for (int i = 1; i <= n; i++) {
        cout << color[i] << " ";
    }
    cout << "\n";
}

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

    int T = 1;

    while (T--) {
        solve();
    }

    return 0;
}