LeetCode题解–133. Clone Graph

链接

LeetCode题目：https://leetcode.com/problems/clone-graph/

难度：Medium

题目

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

该无向图结点包含的信息有整数标签和一个保存所有邻接结点的vector。考虑到邻接结点的存在，可以选用bfs或者dfs进行搜索。我的做法是选用dfs，并且用一个哈希表存储已经拷贝过的结点，每次遍历邻接结点前，都需要将当前结点和拷贝的结点存入哈希表。

分析

为了生成n个数字的所有排列情况，可以先生成后面n-1个数字的所有排列情况，然后第1个数字插到任意位置。而生成n-1个数字的排列也可以先从生成n-2个数字开始，以此类推，最后生成1个数字的排列情况只需要返回该数字。

代码

class Solution { private: map<UndirectedGraphNode *, UndirectedGraphNode *> copy_map; public: UndirectedGraphNode *cloneNode(UndirectedGraphNode *node) { if (copy_map.find(node) != copy_map.end()) return copy_map[node]; auto new_node = new UndirectedGraphNode(node->label); copy_map[node] = new_node; for (auto x:node->neighbors) { new_node->neighbors.push_back(cloneNode(x)); } return new_node; } UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if (node == nullptr) return nullptr; cloneNode(node); return copy_map[node]; } };