如何为特定分组图节点生成满足连接规则的唯一三元编码？

给定整数N，存在两组对象：

• 组1：编号1到N的对象，组内所有对象两两相连
• 组2：编号N+1到2N的对象，组内所有对象两两相连

另有一个长度为p（1 ≤ p ≤ N²）的连接列表，每个元素为[a, b]，其中a属于组1，b属于组2，表示a与b必须相连；列表中未出现的[a, b]对则不能存在连接。

需要为每个对象分配唯一的编码：

• 编码由字符{A, B, C}组成，长度不超过M（N+1 ≤ M ≤ 3N）
• 规则：若两个等长编码x和y存在某个索引i，使得x_i == y_i，则对应对象之间存在连接；反之，若编码在所有索引位置的字符都不相同，则对象之间无连接。

我尝试从跨组连接的编码字符入手，编写了如下代码：

#include <iostream>
#include <vector>
#include <set>

using namespace std;

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

    int n, p, M;
    cin >> n >> p >> M;

    set<int> groups;
    set<pair<int, int>> connections;
    for (int i = 0; i < p; ++i)
    {
        int a, b;
        cin >> a >> b;

        groups.insert(b);
        connections.insert({a, b});
    }

    vector<string> codes(2 * n + 1, string(M, ' '));
    int pos = 1;
    set<int> a_pos;
    for (const int b : groups)
    {
        for (int a = 1; a <= n; ++a)
        {
            if (connections.find({a, b}) == connections.end())
                continue;

            codes[a][pos] = 'A';
            codes[b][pos] = 'A';
        }

        ++pos;
        a_pos.insert(pos);
    }
}

我的思路是：以组2的对象为端点分组处理连接，比如N=3时，若存在连接1→4、2→4，就用同一位置的'A'同时连接1、2与4，同时假设编码始终使用最大长度M。但目前无法保证所有编码的唯一性，即便注意到结构类似二分图也没有思路，该如何解决？

注：此为第三十一届波兰信息学奥林匹克（XXI Polish Olympiad in Informatics）第一轮的Satelity问题。

要同时满足连接规则和编码唯一性，可分三部分构建编码，利用{A,B,C}的区分性覆盖所有要求：

1. 先实现组内两两相连的基础规则 #

组1/组2内所有对象必须两两相连，意味着组内任意两个对象的编码至少有一个位置字符相同，同时要避免组1和组2对象无意义的连接：

• 组1所有对象的第1位设为'A'，组2所有对象的第1位设为'C'——这样组1内任意两个对象在第1位字符相同，满足组内相连；且组1和组2对象在第1位无交集，不会产生额外连接
• 组2所有对象的第2位设为'B'，组1所有对象的第2位设为'C'——同理满足组2内两两相连，同时和组1对象的第2位无交集

2. 实现跨组连接的精准控制 #

你的分组思路可以保留，但需要优化位置分配和非连接对象的字符设置：

• 从第3位开始，为每个组2的对象b分配专属的编码位置pos
• 对于组1中需要和b连接的a，将a和b的pos位都设为'A'
• 对于组1中不需要和b连接的a，将a的pos位设为'B'（确保和b的'A'或默认字符不同）
• 组2对象b的非连接位置保持默认字符（比如'C'），这样无连接的a和b在所有位置都不会有相同字符，符合规则

3. 添加唯一标识位保证编码唯一性 #

利用M≥N+1的长度限制，给每个对象分配一个专属的特征位：

• 组1的对象i，在第i+2位设为'B'（其他位置保持默认'C'）
• 组2的对象j（j=N+i），在第N+2+i位设为'A'（其他位置保持默认'C'）
  这样每个对象的编码都会有一个独有的字符位置，确保所有编码唯一。

代码调整示例 #

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

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

    int n, p, M;
    cin >> n >> p >> M;

    unordered_map<int, unordered_set<int>> b_to_as;
    for (int i = 0; i < p; ++i)
    {
        int a, b;
        cin >> a >> b;
        b_to_as[b].insert(a);
    }

    // 初始化编码为全'C'
    vector<string> codes(2 * n + 1, string(M, 'C'));

    // 组1内相连：第1位设为'A'
    for (int a = 1; a <= n; ++a)
    {
        codes[a][0] = 'A';
        codes[a][1] = 'C'; // 和组2第2位的'B'区分
    }

    // 组2内相连：第2位设为'B'
    for (int b = n+1; b <= 2*n; ++b)
    {
        codes[b][0] = 'C'; // 和组1第1位的'A'区分
        codes[b][1] = 'B';
    }

    // 处理跨组连接，从第3位开始分配位置
    int pos = 2;
    for (auto& [b, as] : b_to_as)
    {
        if (pos >= M) break; // 不超过M长度限制
        // 给需要连接的a和b设为'A'
        for (int a : as)
        {
            codes[a][pos] = 'A';
            codes[b][pos] = 'A';
        }
        // 不需要连接的a设为'B'，确保和b的'A'/'C'不同
        for (int a = 1; a <= n; ++a)
        {
            if (!as.count(a))
            {
                codes[a][pos] = 'B';
            }
        }
        pos++;
    }

    // 添加唯一标识位，确保编码唯一
    // 组1的专属位：第3到第n+2位
    for (int a = 1; a <= n; ++a)
    {
        int unique_pos = a + 2;
        if (unique_pos >= M) break;
        codes[a][unique_pos] = 'B';
    }
    // 组2的专属位：第n+3到第2n+2位
    for (int i = 1; i <= n; ++i)
    {
        int b = n + i;
        int unique_pos = n + 2 + i;
        if (unique_pos >= M) break;
        codes[b][unique_pos] = 'A';
    }

    // 输出编码
    for (int i = 1; i <= 2*n; ++i)
    {
        cout << codes[i] << '\n';
    }

    return 0;
}

内容的提问来源于stack exchange，提问作者Szyszka947