题目描述

本题要求复制一个无向图，图中每个节点都包含一个标签和它的邻居列表
我们无向图用以下的方法序列化：
节点的标签是互不相同的，
我们使用“#”作为节点之间的分隔符，使用“,”作为节点标签和节点的节点邻居的分隔符。
例如：现在有一个序列化的无向图{0,1,2#1,2#2,2}.
这个无向图一共有3个节点，因此序列被#分隔成三部分
第一个节点的标签是0，节点0和节点1，节点2之间有边
第二个节点的标签是1，节点1和节点2之间有边
第三个节点的标签是2，节点2和节点2（它自己）之间有边，形成了自环

我们看到了这个题之后，有什么想法呢，这个无向图，和链表，和二叉树有什么区别呢，其实没有本质的区别，无非是另外一种结构罢了。那么我们如何复制呢，本题的解法就涉及到两个知识点

1. 无向图如何能遍历完全？深度优先遍历DFS，把图的节点先复制下来。
2. 用map保存旧节点和新节点的映射关系。
   一些细节呢，比如DFS通过递归实现，map用的是unordered_map<>实现，unordered_map中的元素，first是key，second是value。

下面就是代码，整体来说没有多少难度

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
    void dfs(UndirectedGraphNode* node){
        if(node==nullptr) return;
        if(mp.count(node)) return;
        auto cpyNode = new UndirectedGraphNode(node->label);
        mp[node] = cpyNode;
        for (auto subnode:node->neighbors){
            dfs(subnode);
        }
    }
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        auto oldNode = node;
        dfs(node);
        for (auto item:mp){
            auto first = item.first;
            for(int i=0;i < first->neighbors.size();i++){
                item.second->neighbors.push_back(mp[first->neighbors[i]]);
            }
        }
        return mp[oldNode];
    }
};