/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null) return null;
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
HashMap map = new HashMap();
map.put(node,newNode);
Queue queue = new LinkedList();
queue.add(node);
while(!queue.isEmpty()){
UndirectedGraphNode current = queue.remove();
List currentNeighbors = current.neighbors;
for(UndirectedGraphNode currentNeighbor: currentNeighbors){
if(map.containsKey(currentNeighbor)){
map.get(current).neighbors.add(map.get(currentNeighbor));
} else{
UndirectedGraphNode copy = new UndirectedGraphNode(currentNeighbor.label);
map.put(currentNeighbor,copy);
queue.add(currentNeighbor);
map.get(current).neighbors.add(copy);
}
}
}
return newNode;
}
}