Clone Graph

犯错：queue循环里，在循环邻居列表时，应该在map里没有含有这个node的时候加入queue，对每一邻居，应该执行加到新node的邻居里的操作

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors. OJ's undirected graph serialization (so you can understand error output):

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.

?I believe the time complexity is O(VE) in the worst case, where V is the # of nodes and E is the number of Edges(connections). I want to say space complexity would be O(V) in the worst case, since there can be a node that is connected to all other nodes.

time O(v+e), space o(n)

first of all, I will use a map to save the mapping from old graph node to new graph node and use a queue to iterator the old graph. When a queue poll out a node, I will get the list of its neighbors. for each of the neighbor, if the neighbor is not in the map, it means we need to copy this node, otherwise, node was copied. then I will get the new node mapping to the node which is just polll out, add the neighbor to it. the new neighbor should be the mapping of the old neighbors.

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)
            return null;
        
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        
        queue.offer(node);
        
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        map.put(node, new UndirectedGraphNode(node.label));
        
        while(!queue.isEmpty()){
            UndirectedGraphNode ud = queue.poll();
            
            List<UndirectedGraphNode> nbList = ud.neighbors;
            
            for(UndirectedGraphNode item: nbList){
                if(!map.containsKey(item)){
                    map.put(item, new UndirectedGraphNode(item.label));
                    queue.offer(item);
                }
                
                
                //copy nb
                // copy neighbor
                map.get(ud).neighbors.add(map.get(item));
            }
            
        }
        
        return map.get(node);
    }
}