EP133 Clone Graph

思路：

一般这种遍历都可以通过BFS或者DFS完成，我们首先通过BFS，但是需要记住哪些节点已经拷贝过了，类似于visited，我们可以用
map<Node, Node> m 的一个map来记住哪些已经拷贝了。

具体的代码如下：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        
        Node* copy = new Node(node->val, {});
        
        m[node] = copy;
        
        stack<Node*> s;
        
        s.push(node);
        
        while (!s.empty()) {
            Node* tmp = s.top();
            s.pop();
            
            for (auto neighbor : tmp->neighbors) {
                if (m.find(neighbor) == m.end()) {
                    s.push(neighbor);
                    m[neighbor] = new Node(neighbor->val, {});
                }
                m[tmp]->neighbors.push_back(m[neighbor]);
            }
        }
        
        return copy;
    }
    
private:
    
    map<Node*, Node*> m;
};

DFS:

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return NULL;
        }
        if (copies.find(node) == copies.end()) {
            copies[node] = new Node(node -> val, {});
            for (Node* neighbor : node -> neighbors) {
                copies[node] -> neighbors.push_back(cloneGraph(neighbor));
            }
        }
        return copies[node];
    }
private:
    unordered_map<Node*, Node*> copies;
};