Leetcode 133 - clone graph

Leetcode133_CloneGraph_studyDiscussion.Java

/*
Leetcode 133: Clone graph

One way to learn the algorithm is to go over the algorithm with the analysis, I like to review word by word so 
that I can carefully follow the thinking process one more time. 

https://leetcode.com/problems/clone-graph/discuss/42313/7-17-lines-C++-BFSDFS-Solutions

**** a hashmap data structure is needed for mapping *****
Graph algorithm has two most popular techniques, which are Bread-First Search (BFS) and Depth-First Search (DFS). 

In order to clone a graph, you need to have a copy of each node in the original graph. Let us go over an example
together. 

Suppose we are given a graph {0, 1 # 1, 0}. We know that the graph has two nodes 0 and 1 and they are connected 
to each other.

We now start from 0. We make a copy of 0. Then we check 0's neighbors and we see 1. We make a copy of 1 and we 
add the copy to the neighbors of the copy of 0. Now the cloned graph is {0 (copy), 1 (copy)}. Then we visit 1. 
We make a copy of 1… well, wait, why do we make another copy of it? We already have one! Note that if you make 
a new copy of the node, these copies are not the same and the graph structure will be wrong! 

In fact, we need to maintain a mapping from each node to its copy. If the node has an existed copy, we simply use
it. So in the above example, the remaining process is that we visit the copy of 1 and add the copy of 0 to its 
neighbors and the cloned graph is eventually {0 (copy), 1 (copy) # 1 (copy), 0 (copy)}.

Note that the above process uses BFS. Of course, you can use DFS. The key is the node-copy mapping, anyway.
*/
class Solution {
public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (!node) 
          return NULL;
          
        UndirectedGraphNode* copy = new UndirectedGraphNode(node -> label);
        mp[node] = copy;
        queue<UndirectedGraphNode*> toVisit;
        toVisit.push(node);
        
        while (!toVisit.empty()) {
            UndirectedGraphNode* cur = toVisit.front();
            toVisit.pop();
            for (UndirectedGraphNode* neigh : cur -> neighbors) {
                if (mp.find(neigh) == mp.end()) {
                    UndirectedGraphNode* neigh_copy = new UndirectedGraphNode(neigh -> label);
                    mp[neigh] = neigh_copy;
                    toVisit.push(neigh);
                }
                
                mp[cur] -> neighbors.push_back(mp[neigh]);
            }
        }
        
        return copy; 
    }
    
private:
    unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
};