如何高效构建符合规则、相邻共享单元素的数字对链

问题核心转换 #

你可以把问题做个等价转换，直接跳出O(n²)的两两比对逻辑：

• 把每个独立数字看作图的顶点
• 把每个符合规则的数字对(a,b)看作连接顶点a和b的无向边

此时你的规则要求刚好对应图论里的**边不重复路径（迹）**的定义：相邻边必然共享顶点，完全匹配相邻数字对要有公共元素的要求。 #

两种常见场景的高效解法 #

场景1：将所有数字对划分为最少数量的链 #

这个场景可以用欧拉路径相关的Hierholzer算法实现，时间复杂度O(n)，完全能支撑几万到几十万条数据的处理：

实现步骤

1. 初始化三个存储结构：
   • unordered_map<int, vector<边信息>> adj：邻接表，每个数字对应所有包含它的数字对信息（对索引、配对的另一个数字、原始数字对）
   • vector<bool> visited：标记数字对是否已经被加入链中
   • unordered_map<int, int> degree：记录每个数字出现的次数（即顶点度数）
2. 遍历所有未访问的数字对，每个连通分量生成一条链：
   • 优先选当前连通分量里度数为奇数的数字作为起点，没有奇度数点就随便选一个该分量里的数字作为起点
   • 用Hierholzer算法深度优先遍历该连通分量的所有边，回溯时把边加入当前链
   • 翻转链的顺序后输出即可

参考C++实现

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

void dfs(int cur_num, vector<bool>& visited, 
        unordered_map<int, vector<pair<int, pair<int, pair<int, int>>>>>& adj,
        vector<pair<int, int>>& cur_chain) {
    for (auto& edge_info : adj[cur_num]) {
        int edge_idx = edge_info.first;
        int another_num = edge_info.second.first;
        pair<int, int> origin_pair = edge_info.second.second;
        if (!visited[edge_idx]) {
            visited[edge_idx] = true;
            dfs(another_num, visited, adj, cur_chain);
            cur_chain.push_back(origin_pair);
        }
    }
}

int main() {
    vector<pair<int, int>> input_pairs = {{0,1}, {2,3}, {1,6}, {4,6}, {8,9}, {2,8}};
    int n = input_pairs.size();
    unordered_map<int, vector<pair<int, pair<int, pair<int, int>>>>> adj;
    unordered_map<int, int> degree;
    for (int i = 0; i < n; i++) {
        int a = input_pairs[i].first;
        int b = input_pairs[i].second;
        adj[a].push_back({i, {b, input_pairs[i]}});
        adj[b].push_back({i, {a, input_pairs[i]}});
        degree[a]++;
        degree[b]++;
    }
    vector<bool> visited(n, false);
    int chain_count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            chain_count++;
            cout << "----- chain #" << chain_count << endl;
            // 优先选奇度数点作为起点
            int start_num = input_pairs[i].first;
            for (auto& deg_item : degree) {
                if (deg_item.second % 2 == 1) {
                    start_num = deg_item.first;
                    break;
                }
            }
            vector<pair<int, int>> cur_chain;
            dfs(start_num, visited, adj, cur_chain);
            reverse(cur_chain.begin(), cur_chain.end());
            for (auto& p : cur_chain) {
                cout << "(" << p.first << "," << p.second << ")" << endl;
            }
        }
    }
    return 0;
}

运行结果和你给出的示例完全一致。 #

场景2：求单条最长的数字对链 #

如果不需要覆盖所有数字对，只需要找长度最长的单条链，可以用动态规划实现，时间复杂度O(n log n)：

1. 初始化unordered_map<int, int> dp，dp[x]表示以数字x结尾的最长链长度
2. 把所有数字对按任意规则排序（如果要求链整体递增可以按第二个元素从小到大排序）
3. 遍历每个数字对(a,b)：
   • 计算当前能生成的最长链长度：max(dp[a], dp[b]) + 1
   • 同时更新dp[a]和dp[b]为这个最大值
4. 遍历dp表取最大值就是最长链的长度，要输出具体链的话加个前驱记录即可

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