节点编号不连续的无向图在C++中的构建方法

核心思路 #

• 用map<int, int>维护原节点编号到连续新编号的映射，每次遇到未记录的原节点，分配一个递增的新编号（从1或0开始均可）
• 采用动态邻接表vector<vector<int>>替代固定大小数组，避免空间浪费，同时适配任意数量的节点

完整实现代码 #

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
    int e;
    cin >> e;

    // 原节点→新编号的映射
    map<int, int> node_to_id;
    // 新编号→原节点的反向映射（可选，用于后续遍历查询）
    vector<int> id_to_node;
    // 动态邻接表
    vector<vector<int>> adj;
    // 当前可用的新编号，从1开始（习惯0起始可改为0）
    int current_id = 1;

    for (int i = 0; i < e; ++i) {
        int u, v;
        cin >> u >> v;

        // 处理节点u的映射
        if (node_to_id.find(u) == node_to_id.end()) {
            node_to_id[u] = current_id;
            id_to_node.push_back(u);
            adj.resize(current_id + 1); // 适配1-based编号，adj索引0可闲置
            current_id++;
        }
        // 处理节点v的映射
        if (node_to_id.find(v) == node_to_id.end()) {
            node_to_id[v] = current_id;
            id_to_node.push_back(v);
            adj.resize(current_id + 1);
            current_id++;
        }

        // 转换为新编号并添加无向边
        int u_new = node_to_id[u];
        int v_new = node_to_id[v];
        adj[u_new].push_back(v_new);
        adj[v_new].push_back(u_new);
    }

    // 示例：遍历转换后的邻接表（含原编号对应关系）
    cout << "转换后的邻接表：\n";
    for (int i = 1; i < current_id; ++i) {
        cout << "新编号" << i << "（原编号：" << id_to_node[i-1] << "）的邻接节点：";
        for (int neighbor : adj[i]) {
            cout << neighbor << " ";
        }
        cout << "\n";
    }

    return 0;
}

关键细节说明 #

• 映射逻辑：map自动判断节点是否已存在，避免重复分配编号；反向映射id_to_node可以快速通过新编号找到原节点，比遍历map效率更高
• 邻接表扩容：用adj.resize()动态调整大小，1-based编号下索引0可闲置，避免数组越界
• 适用性：支持任意大的原节点编号（比如原编号是1e9级别的），不会像固定数组那样浪费空间或无法适配

输入输出示例 #

输入（对应题目中的边集合）：

3
1 3
6 7
3 7

输出：

转换后的邻接表：
新编号1（原编号：1）的邻接节点：2 
新编号2（原编号：3）的邻接节点：1 4 
新编号3（原编号：6）的邻接节点：4 
新编号4（原编号：7）的邻接节点：3 2 

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