题解：特工分组问题

题意分析

我们需要将$A$名特工（编号$0$到$A-1$）分成最多$3$个小组，满足以下约束条件：

1. 互相厌恶的特工不能分在同一组（输入给出$R$对厌恶关系）
2. 组织中存在$1$到$3$个"坏家伙"特工
3. 每个普通特工至少厌恶一个"坏家伙"

这实际上是一个图的$3$-着色问题：

• 特工 = 图中的顶点
• 厌恶关系 = 图中的边
• 小组 = 颜色（$0,1,2$）

解题思路

1. 问题转化：

   • 将问题转化为判断图是否是$3$-可着色的（即能否用最多$3$种颜色给顶点着色，使相邻顶点颜色不同）
   • 这是一个经典的NP完全问题，但对于$A \leq 500$的规模，可以通过优化回溯法解决

2. 关键观察：

   • "坏家伙"特工的存在会影响普通特工的着色选择
   • 每个普通特工至少与一个"坏家伙"特工相邻（即至少有一条边连接普通特工和坏家伙）

3. 算法选择：

   • 回溯法：尝试为每个顶点分配颜色，遇到冲突时回溯
   • 优化策略：
     • 按顶点度数从高到低的顺序处理（尽早处理约束最多的顶点）
     • 使用前向检查（提前排除会导致冲突的颜色选择）

4. 实现步骤：

   • 构建图的邻接表表示
   • 计算每个顶点的度数并排序
   • 按排序顺序尝试$3$种颜色的分配
   • 使用递归回溯搜索可行解

复杂度分析

• 最坏情况下时间复杂度为$O(3^A)$
• 但通过优化（顶点排序、前向检查），实际运行时间对于$A=500$也是可行的
• 空间复杂度为$O(A^2)$（存储邻接矩阵）

示例解释

对于样例输入1：

3 3
0 1
0 2
2 1

这是一个完全图$K_3$，需要$3$种颜色才能正确着色，因此输出：

0 1 2

而对于：

4 6
0 1
0 2
0 3
1 2
1 3
2 3

这是完全图$K_4$，无法用$3$种颜色着色，输出：

The agents cannot be split

标程

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

bool isSafe(size_t node, int color, const vector<vector<int> >& graph, const vector<int>& colors) {
    for (size_t i = 0; i < graph[node].size(); ++i) {
        size_t neighbor = graph[node][i];
        if (colors[neighbor] == color) {
            return false;
        }
    }
    return true;
}

bool graphColoringUtil(size_t node, vector<int>& colors, const vector<vector<int> >& graph, int maxColors, const vector<size_t>& order) {
    if (node == graph.size()) {
        return true;
    }
    size_t current = order[node];
    for (int c = 0; c < maxColors; ++c) {
        if (isSafe(current, c, graph, colors)) {
            colors[current] = c;
            if (graphColoringUtil(node + 1, colors, graph, maxColors, order)) {
                return true;
            }
            colors[current] = -1;
        }
    }
    return false;
}

bool graphColoring(const vector<vector<int> >& graph, vector<int>& colors, int maxColors) {
    size_t n = graph.size();
    vector<pair<int, size_t> > degrees;
    for (size_t i = 0; i < n; ++i) {
        degrees.push_back(make_pair(-static_cast<int>(graph[i].size()), i));
    }
    sort(degrees.begin(), degrees.end());
    vector<size_t> order;
    for (size_t i = 0; i < degrees.size(); ++i) {
        order.push_back(degrees[i].second);
    }
    return graphColoringUtil(0, colors, graph, maxColors, order);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int A, R;
    while (cin >> A >> R) {
        if (A == 0 && R == 0) break;
        vector<vector<int> > graph(A);
        for (int i = 0; i < R; ++i) {
            int a1, a2;
            cin >> a1 >> a2;
            graph[a1].push_back(a2);
            graph[a2].push_back(a1);
        }
        vector<int> colors(A, -1);
        if (graphColoring(graph, colors, 3)) {
            for (size_t i = 0; i < colors.size(); ++i) {
                if (i != 0) cout << " ";
                cout << colors[i];
            }
            cout << endl;
        } else {
            cout << "The agents cannot be split" << endl;
        }
    }
    return 0;
}