LeetCode 133. 克隆图

LeetCode 133. 克隆图

思路：

题目要求不能返回原点，所以要开个哈希表，把原始点映射到它的复制点，这样哈希表里面存的是复制的点，然后再去复制原始点的边，就是它的邻居。

代码：

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    unordered_map<Node*,Node*> h;
    Node* cloneGraph(Node* node) {
        if(!node) return nullptr;
        //复制所有边 映射到哈希表
        dfs(node);

        //复制所有边

        for(auto i : h){
            //复制所有原始点与邻居的边
            for(auto ver : i.first->neighbors){
                i.second->neighbors.push_back(h[ver]);
            }
        }

        return h[node];

    }

    void dfs(Node *node){
        h[node] = new Node(node->val);
        //复制它的邻居
        for(auto i : node->neighbors){
            if(h.count(i) == 0){
                dfs(i);
            }
        }
    }
};