/*

 // Definition for a Node.

 class Node {

 public:

     int val;

     vector<Node*> neighbors;

     Node() {}

     Node(int _val, vector<Node*> _neighbors) {

         val = _val;

         neighbors = _neighbors;

     }

 };

 */

 class Solution {

 public:

     Node* cloneGraph(Node* node) {

         if (!node) {return node;}

         unordered_map<Node*, Node*> memo;

         Node* copy = new Node(node->val,  vector<Node*>{});

         memo[node] = copy;

         queue<Node*> que;

         que.push(node);

         unordered_set<Node*> visit;

         visit.insert(node);

         while (!que.empty()) {

             Node* cur = que.front(); que.pop();

             Node* copyCur = memo[cur];

             for (auto& adj : cur->neighbors) {

                 if (memo.find(adj) == memo.end()) {

                     Node* copyAdj = new Node(adj->val, vector<Node*>{});

                     memo[adj] = copyAdj;

                 }

                 copyCur->neighbors.push_back(memo[adj]);

                 if (visit.find(adj) == visit.end()) {

                     visit.insert(adj);

                     que.push(adj);

                 }

             }

         }

         return copy;

     }

 };