力扣(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);
}
};
- 时间复杂度 : O ( ∑ i = 0 n m i ) O(\sum_{i=0}^{n} m_i) O(∑i=0nmi) ， n n n 是点的数量， m m m 是边的数量，遍历所有点的所有边，时间复杂度 O ( ∑ i = 0 n m i ) O(\sum_{i=0}^{n} m_i) O(∑i=0nmi) 。
- 空间复杂度 : O ( n ) O(n) O(n) ， 哈希表存 n n n 个点的空间复杂度 O ( n ) O(n) O(n) 。
AC
