题目描述

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

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

class Node {
    public int val;
    public List<Node> neighbors;
}

样例

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

算法1

(BFS) $O(m)$

用哈希表记录旧节点到新节点的映射关系；
然后BFS遍历旧节点，遍历过程中建立新老节点的映射关系，并且根据老节点的拓扑关系，建立新节点的拓扑关系。

时间复杂度

将所有边遍历重建了一次，所以是$O(m)$。

参考文献

C++ 代码

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node *, Node *> o2n;

        Node * nnode = new Node(node->val); 
        o2n[node] = nnode;
        queue<Node *> Q; Q.push(node);

        while (Q.size()){
            Node *tail = Q.front(); Q.pop();
            for (Node *head: tail->neighbors){
                if (!o2n.count(head)){
                    Node *n_head = new Node(head->val);
                    o2n[head] = n_head;
                    Q.push(head);
                }
                o2n[tail]->neighbors.push_back(o2n[head]);
            }
        }

        return o2n[node];
    }
};