力扣(LeetCode)133. 克隆图(C++)

dfs+哈希表+图

先深搜建立所有点，加入哈希表。再遍历哈希表，按照拷贝前后的结点，拷贝边。最后返回某一结点，即为所求。

class Solution {
public:
    unordered_map<Node*,Node*> mp;
    Node* cloneGraph(Node* node) {
        if(!node) return node;
        dfs(node);
        for(auto &[s,d]:mp)
            for(auto &e:s->neighbors)
                d->neighbors.push_back(mp[e]);
        return mp[node];
    }
    void dfs(Node *node) {
        mp[node] = new Node(node->val);
        for(auto &v:node->neighbors)
            if(!mp.count(v)) dfs(v);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1. 时间复杂度 : $O({\sum }_{i=0}^n{m}_i)$ ， $n$ 是点的数量，$m$ 是边的数量，遍历所有点的所有边，时间复杂度 $O({\sum }_{i=0}^n{m}_i)$ 。
2. 空间复杂度 : $O(n)$ ， 哈希表存 $n$ 个点的空间复杂度 $O(n)$ 。

AC