# 133. Clone Graph

## 1.問題

* 給予一個graph

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNZFcp09zs3Rg5-R4eR%2F-LNZ8cF7dRcMVCZY3ruj%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-29%20%E4%B8%8B%E5%8D%883.06.14.png?alt=media\&token=45045907-8ad8-4941-a5c1-a1dd672a2f3a)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
* function header, parameter
* test input
* 觀察
  * 這題跟138. Copy List with Random Pointer很像, 用map儲存已經複製過的node, 避免重複拷貝, 重複走訪
* 說明想法
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
/**
 * 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;
    }
};
```