Untitled

class Solution {

public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        Node first {-1};

        unordered_set<Node*> vis;
        queue<pair<Node*, Node*>> q;
        q.push({node, &first});

        while (!q.empty()) {
            auto [cur, par] = q.front();
            q.pop();
            if (vis.count(cur)) continue;

            vis.insert(cur);

            Node* newNode = new Node(cur->val);
            par->neighbors.push_back(newNode);

            for (auto c : cur->neighbors) {
                if (vis.count(c)) continue;
                q.push({c, newNode});
            }
        }

        return first.neighbors.back();
    }
};