Leetcode/各大家 -- 133. Clone Graph(BFS)

133. Clone Graph(BFS)
medium
https://leetcode.com/problems/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
         / \
         \_/

 Pocket Gems Google Uber Facebook

思路： Create HashMap to match each node from old graph to new graph.
           Use BFS to travel each node in old graph. Create corresponding node (copy) in hashmap for new graph on the fly.
           Then add each neighbor of current node to the matching node in new graph (here need to get(key) for a copy) 
Complexity: O(N) visit each node only once.  Space O(N)

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)return node;
        Queue<UndirectedGraphNode> qu = new LinkedList<UndirectedGraphNode>();//travel node in old graph
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<>();//<node in old graph,node in new graph>
        UndirectedGraphNode root = new UndirectedGraphNode (node.label);
        map.put(node,root);
        qu.add(node);
        while(!qu.isEmpty()){
            UndirectedGraphNode cur = qu.remove();
            for (UndirectedGraphNode oldn: cur.neighbors){
                if(!map.containsKey(oldn)){
                    map.put(oldn, new UndirectedGraphNode(oldn.label));
                    qu.add(oldn);
                }
                map.get(cur).neighbors.add(map.get(oldn));//need to add nodes in new graph
            }
        }
        return root;
    }
}