题目描述

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

提示：

1. 节点数介于 1 到 100 之间。

2. 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。

3. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。

4. 必须将给定节点的拷贝作为对克隆图的引用返回。

样例

输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

算法1

(DFS) $O(n)$

递归地访问(复制)邻居节点，用一个map来存储节点访问情况

C++ 代码

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> hash;

    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) return 0;
        auto root = new UndirectedGraphNode(node->label);
        hash[node] = root;
        dfs(node);
        return root;
    }

    void dfs(UndirectedGraphNode* node)
    {
        for (auto &neighbor : node->neighbors)
        {
            if (!hash.count(neighbor))
            {
                hash[neighbor] = new UndirectedGraphNode(neighbor->label);
                dfs(neighbor);
            }
            hash[node]->neighbors.push_back(hash[neighbor]);
        }
    }
};