链接
https://leetcode-cn.com/problems/clone-graph/
耗时
解题:0.5 day
题解:13 min
题意
给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
测试用例格式:
简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
思路
BFS 遍历一遍原图,遍历的同时建新图。为方便的找到每个节点,所有节点的指针均用 哈希表 存储。BFS 暴搜时,遇到 哈希表 中没有的节点即新建并放入哈希表中,遇到的每条边都在新图中连接上,并且遍历过的每个点都用 vis 哈希表存储,即每个节点只访问一次。
时间复杂度:
O
(
V
+
E
)
O(V+E)
O(V+E)
AC代码
class Solution {
public:
Node* cloneGraph(Node* node) {
if(!node) return NULL;
unordered_map<int, Node*> nodemap;
unordered_set<int> vis;
queue<Node*> q;
q.push(node);
Node* head = new Node(node->val);
nodemap.insert(make_pair(node->val, head));
while(!q.empty()) {
Node* now = q.front();
q.pop();
if(vis.find(now->val) != vis.end()) continue;
vis.insert(now->val);
for(auto nei : now->neighbors) {
if(nodemap.find(nei->val) == nodemap.end()) {
Node* t = new Node(nei->val);
nodemap.insert(make_pair(nei->val, t));
}
nodemap[now->val]->neighbors.push_back(nodemap[nei->val]);
q.push(nei);
}
}
return head;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)