1 /*
2 // Definition for a Node.
3 class Node {
4 public:
5 int val;
6 vector neighbors;
7
8 Node() {}
9
10 Node(int _val, vector _neighbors) {
11 val = _val;
12 neighbors = _neighbors;
13 }
14 };
15 */
16 class Solution {
17 public:
18 Node* cloneGraph(Node* node) {
19 if (!node) {return node;}
20 unordered_map memo;
21 Node* copy = new Node(node->val, vector{});
22 memo[node] = copy;
23 queue que;
24 que.push(node);
25 unordered_set visit;
26 visit.insert(node);
27 while (!que.empty()) {
28 Node* cur = que.front(); que.pop();
29 Node* copyCur = memo[cur];
30 for (auto& adj : cur->neighbors) {
31 if (memo.find(adj) == memo.end()) {
32 Node* copyAdj = new Node(adj->val, vector{});
33 memo[adj] = copyAdj;
34 }
35 copyCur->neighbors.push_back(memo[adj]);
36 if (visit.find(adj) == visit.end()) {
37 visit.insert(adj);
38 que.push(adj);
39 }
40 }
41 }
42 return copy;
43 }
44 };