Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution:
Clone is a type of deep copy.
What is deep copy? deep vs shallow copy
To my knowledge, shallow copy means you only copy a reference, and you share the same memory with another reference, however, we will get to a different memory with same content in deep copy.
It is a graph traverse question, at the first, we make it sure that the graph is directed. Since 0 can go to but 2 cannot go back to 0. 

Use a Hash Map <old graph node -> new graph node> to mark visited nodes, so we can avoid loops.

// build the clone graph recursively, it has same logic as "copy list with random pointer"
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode root) {
        HashMap map = new HashMap();
        return helper(root, map);
    }
    public UndirectedGraphNode helper(UndirectedGraphNode root, HashMap map) {
        if(root == null)
            return root;
        if(map.containsKey(root))
            return map.get(root);
            
        UndirectedGraphNode node = new UndirectedGraphNode(root.label);
        map.put(root, node);
        for(UndirectedGraphNode tmp : root.neighbors)
            node.neighbors.add(helper(tmp, map));
            
        return node;
    }
}