1 /**
 2  * Definition for undirected graph.
 3  * class UndirectedGraphNode {
 4  *     int label;
 5  *     ArrayList<UndirectedGraphNode> neighbors;
 6  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 7  * };
 8  */
 9 public class Solution {
10     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
11         UndirectedGraphNode newNode = null;
12         if(node != null){
13             Map<UndirectedGraphNode, UndirectedGraphNode> org = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
14             ArrayList<UndirectedGraphNode> alist = new ArrayList<UndirectedGraphNode>();
15             alist.add(node);
16             for(int i = 0; i < alist.size(); ++i){
17                 UndirectedGraphNode temp = alist.get(i);
18                 UndirectedGraphNode cloneNode = null;
19                 if(!org.containsKey(temp)){
20                     cloneNode = new UndirectedGraphNode(temp.label);
21                     org.put(temp, cloneNode);
22                 }
23                 else
24                     cloneNode = org.get(temp);                    
25                 ArrayList<UndirectedGraphNode> nei = temp.neighbors;
26                 for(int j = 0; j < nei.size(); ++j){
27                     if(org.containsKey(nei.get(j)))
28                         cloneNode.neighbors.add(org.get(nei.get(j)));
29                     else{
30                         UndirectedGraphNode clNode = new UndirectedGraphNode(nei.get(j).label);
31                         alist.add(nei.get(j));
32                         org.put(nei.get(j), clNode);
33                         cloneNode.neighbors.add(clNode);
34                     }                            
35                 }
36             }
37             newNode = org.get(node);
38         }
39         return newNode;
40     }
41 }