Clone Graph (Leetcode 133)

DFS Approach:

注意，对于DFS，对map的赋值要在DFS loop开始以前。这样可以避免由于graph有loop而造成的死循环。

Key Point：如果graph有环，将map的赋值建立在loop之前。

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if(!node) return NULL;
        else if(mp.count(node)) return mp[node];
        
        auto node_copy = new UndirectedGraphNode(node->label);
        mp[node] = node_copy;
        for(auto it : node->neighbors){
            node_copy->neighbors.push_back(cloneGraph(it));
        }
        return mp[node];
    }
};

BFS Approach:
虽然长，但BFS写起来也很简单。而且可以避免死循环，以及stack overflow。还是尽量用BFS好了。

/**
 * 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 NULL;
        unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
        queue<UndirectedGraphNode*> q;
        
        auto *node_copy = new UndirectedGraphNode(node->label);
        mp[node] = node_copy;
        q.push(node);
        
        while(!q.empty()){
            auto cur = q.front(); q.pop();
            auto *cur_copy = mp[cur];
            mp[cur] = cur_copy;
            for(auto it :  cur->neighbors){
                if(mp.count(it)){
                    cur_copy->neighbors.push_back(mp[it]);
                }
                else{
                    auto it_copy = new UndirectedGraphNode(it->label);
                    mp[it] = it_copy;
                    cur_copy->neighbors.push_back(it_copy);
                    q.push(it);
                }
            }
            
        }
        return mp[node];
    }
};