133 Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
The Idea: To clone a graph, we will have to copy every node within the graph. However, because each node carries a collection of neighbor that are points, the we need to avoid any extra copying. For example, say our graph is:
1: 1,2
2: 1,3
Even though 1 is connected to itself, and 2 is connect to 1, both these 1s have the same address. So as we iterate through the graph, we need to map the existing address of a node to the address of the copy which is the new node. Only when the memory is not mapped do we create a new node, and when the memory is mapped, we can return the same address which is the copy of the new node.
Complexity: O(n) time and space
/**
* Definition for undirected graph.
* struct UndirectedGraphNode {
* int label;
* vector<UndirectedGraphNode *> neighbors;
* UndirectedGraphNode(int x) : label(x) {};
* };
*/
class Solution {
public:
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
if (!node) return nullptr;
if (!mem.count(node)) {
mem[node] = new UndirectedGraphNode(node->label);
for (auto &neighbor : node->neighbors) {
// we've already mapped the node, so mem[node] references the new address
mem[node]->neighbors.push_back(cloneGraph(neighbor));
}
}
return mem[node];
}
private:
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mem;
};
Last modified 3yr ago