133. Clone Graph

DFS O(n) time O(n) space
这道题一定要preorder先cache再递归，因为有可能存在环

/*
// 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 node;
        if (nodes.count(node)) return nodes[node];
        auto res = new Node;
        nodes[node] = res; // 一定要先cache！！
        res->val = node->val;
        for (auto n : node->neighbors) {
            res->neighbors.push_back(cloneGraph(n));
        }
        return res;
    }

    unordered_map<Node *, Node *> nodes;
};

BFS

/*
// 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 node;
        unordered_map<Node *, Node *> nodes{{node, new Node(node->val, {})}};
        queue<Node *> q{{node}};
        while (!q.empty()) {
            auto x = q.front(); q.pop();
            for (auto n : x->neighbors) {
                if (!nodes.count(n)) {
                    nodes[n] = new Node(n->val, {});
                    q.push(n);
                }
                nodes[x]->neighbors.push_back(nodes[n]);
            }
        }
        return nodes[node];
    }
};