133. Clone Graph

1.問題

• 給予一個graph

2.想法

• 提問

• function header, parameter

• test input

• 觀察

  • 這題跟138. Copy List with Random Pointer很像, 用map儲存已經複製過的node, 避免重複拷貝, 重複走訪

• 說明想法

• 測試計算複雜度

3.程式碼

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        unordered_map<UndirectedGraphNode *, UndirectedGraphNode *> m;
        return getCopyGraph(node, m);
    }
private:
    UndirectedGraphNode * getCopyGraph(UndirectedGraphNode *node, unordered_map<UndirectedGraphNode *, UndirectedGraphNode *>& m) {
        if (!node) {
            return NULL;
        }
        
        if (m.count(node)) {
            return m[node];
        }
        
        UndirectedGraphNode * newNode = new UndirectedGraphNode(node->label);
        m[node] = newNode;
        vector<UndirectedGraphNode *> v;
        for (int i = 0; i < node->neighbors.size(); i++) {
            v.push_back(getCopyGraph(node->neighbors[i], m));
        }
        newNode->neighbors = v;
        
        return newNode;
    }
};