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;
};