图的遍历

该题类似于138题。

主要思想：给每个点创建一个小弟，即将当前点和复制的点建立关系，然后根据当前点和其他点的关系，给复制的点也建立起关系。

如何将原点和复制的点建立关系呢？

通过哈希映射

1.复制所有的点(dfs)

2.复制所有的边

$ 时间复杂度O(N + M) $

参考文献

lc究极班

AC代码

/*
// 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*> hash;

    Node* cloneGraph(Node* node) {
        if (!node) return node;
        dfs(node);//复制所有点

        //复制所有边
        for (auto [old, now] : hash) {
            for (auto ver : old->neighbors){
                now->neighbors.push_back(hash[ver]);
            }
        }
        return hash[node];
    }

    void dfs(Node* node){
        //对于该点，复制一个新点
        hash[node] = new Node(node->val);

        //遍历该点的邻点
        for (auto ver : node->neighbors) {
            if (!hash.count(ver))
                dfs(ver);
        }
    }
};