（每日一练C++）133. 克隆图

矫情吗；* 2023-10-04 18:30 20阅读 0赞

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

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

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

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：

输入：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 。  
示例 2：

输入：adjList = \[\[\]\]  
输出：\[\[\]\]  
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。  
示例 3：

输入：adjList = \[\]  
输出：\[\]  
解释：这个图是空的，它不含任何节点。  
示例 4：

输入：adjList = \[\[2\],\[1\]\]  
输出：\[\[2\],\[1\]\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/clone-graph  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public:
        unordered_map<Node*, Node*> visited;
        Node* cloneGraph(Node* node) {
            if (node == nullptr) {
                return node;
            }
    
            // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
            if (visited.find(node) != visited.end()) {
                return visited[node];
            }
    
            // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
            Node* cloneNode = new Node(node->val);
            // 哈希表存储
            visited[node] = cloneNode;
    
            // 遍历该节点的邻居并更新克隆节点的邻居列表
            for (auto& neighbor: node->neighbors) {
                cloneNode->neighbors.emplace_back(cloneGraph(neighbor));
            }
            return cloneNode;
        }
    };
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/clone-graph/solution/ke-long-tu-by-leetcode-solution/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。