# Leetcode 133: Clone Graph (已解決)

圖為四邊形 : 

1------2
|      |
4------3
    
> adjList = 節點1的鄰居[2,4],節點二的鄰居[1,3],節點三的鄰居[2,4],節點四的鄰居[1,3]

## DFS程式碼

class Solution {
public:
    
    Node* dfs(Node* cur,unordered_map<Node*,Node*> &mp){
        
        vector<Node*> neighbors;
        Node* clone = new Node(cur->val);
        
        mp[cur]=clone;//將複製好的新節點val 放入map 當作key
        
        for(auto it : cur->neighbors){ //在map裡找其鄰居節點
            if(mp.find(it)!=mp.end()){
                neighbors.push_back(mp[it]);//把cur的鄰居放進去向量裡
            }
            else{
                neighbors.push_back(dfs(it,mp));
            }
        }
        clone->neighbors = neighbors;//把鄰居接上去
        return clone;
    }
    
    Node* cloneGraph(Node* node) {
        
        unordered_map<Node*,Node*> mp; //用來放(新節點)與(判斷與遍歷鄰居節點)
        if(node==nullptr)
            return nullptr;
        else if(node->neighbors.size()==0){
            Node* clone = new Node(node->val);
            return clone;
        }
        return dfs(node,mp);
    }
};

Success
Details 
Runtime: 10 ms, faster than 54.91% of C++ online submissions for Clone Graph.
Memory Usage: 9.2 MB, less than 13.28% of C++ online submissions for Clone Graph.

## BFS程式碼

class Solution {
public:
    
    unordered_map<Node*,Node*> mp;
    
    Node* cloneGraph(Node* node) {   
        
        if(node==nullptr) return nullptr;
        
        Node* first = new Node(node->val,{});//複製的第一個新節點，把neighbors去掉，因為之後迴圈會將鄰居放進去
        mp[node]=first;//放進map
        
        queue<Node*> todo;
        todo.push(node);//push帶有鄰居的node節點
        
        while(!todo.empty()){
            
            Node* clone = todo.front();//複製queue裡的節點當作新節點
            todo.pop();
            
            for(auto neighbor : clone->neighbors){//迭代器
                if(mp.find(neighbor)==mp.end()){//判斷map裡是否已經有鄰居節點
                   mp[neighbor] = new Node(neighbor->val,{}); //若沒有，就新增一個鄰居節點放進map
                   todo.push(neighbor); 
                }
                mp[clone]->neighbors.push_back(mp[neighbor]);//每次都把新複製節點的鄰居放進去
            }
        }
        return first;//回傳一開始建立好用來回傳的節點
    }
};

結果 :

Success
Details 
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Clone Graph.
Memory Usage: 8.5 MB, less than 94.59% of C++ online submissions for Clone Graph.