class Solution {
public:
    unordered_map<int, Node*> visited;
    Node* cloneGraph(Node* node) {
        if(node == nullptr) return nullptr;
        if(visited.find(node->val) != visited.end()) {
            return visited[node->val];
        }

        Node* newNode = new Node(node->val);
        visited[node->val] = newNode;

        for(auto neighbor : node->neighbors) {
            newNode->neighbors.emplace_back(cloneGraph(neighbor));
        }
        
        return newNode;
    }
};

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(node == nullptr) return nullptr;
        
        queue<Node*> que;
        unordered_map<int, Node*> visited;

        Node* newNode = new Node(node->val);
        visited[node->val] = newNode;
        que.push(node);

        while(!que.empty()) {
            Node* current = que.front();
            que.pop();

            for(auto neighbor : current->neighbors) {
                // if this point is not visited before
                // create a new node with this value
                if(visited.find(neighbor->val) == visited.end()) {
                    Node* child = new Node(neighbor->val);
                    visited[neighbor->val] = child;
                    que.push(neighbor);
                }
                // insert to the current's neighbors
                visited[current->val]->neighbors.emplace_back(visited[neighbor->val]);
            }
        }

        return visited[node->val];
    }
};