/*
// 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 {
private:
unordered_map<Node*, Node*> visited;
public:
Node* cloneGraph(Node* node) {
if (node == nullptr) return node;
// If the node has already been accessed, the corresponding clone is returned directly from the hash table
if (visited.count(node)) return visited[node];
// Clone the node, noting that for deep copy we will not clone the list of its neighbors
Node* clone = new Node(node->val);
visited[node] = clone;
// Iterate through the neighbors of this node and update the neighbor list of the cloned node
for (auto& neighbor : node->neighbors) {
clone->neighbors.emplace_back(cloneGraph(neighbor));
}
return clone;
}
};