133. Clone Graph

133. Clone Graph.java

/**
 * 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) {
        return helper(node);
    }
    
    public UndirectedGraphNode helper(UndirectedGraphNode node){
 
        if(node==null){
            return null;
        }
        ArrayList<UndirectedGraphNode> currentList = new ArrayList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
        HashMap<UndirectedGraphNode,UndirectedGraphNode> visited = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
        currentList.add(node);
        
        while(currentList.size()>0){
            ArrayList<UndirectedGraphNode> next = new ArrayList<UndirectedGraphNode>();
            for(int i=0;i<currentList.size();i++){
                if(visited.get(currentList.get(i))==null){
                    
                    if(map.get(currentList.get(i))!=null){
                        visited.put(currentList.get(i),map.get(currentList.get(i)));
                    } else {
                        map.put(currentList.get(i), new UndirectedGraphNode(currentList.get(i).label));
                        visited.put(currentList.get(i), map.get(currentList.get(i)));
                    }
                    
                    for(int j=0;j<currentList.get(i).neighbors.size();j++){
                        if(map.get(currentList.get(i).neighbors.get(j))==null){
                            map.put(currentList.get(i).neighbors.get(j),new UndirectedGraphNode(currentList.get(i).neighbors.get(j).label));
                        }
                        visited.get(currentList.get(i)).neighbors.add(map.get(currentList.get(i).neighbors.get(j)));
                        next.add(currentList.get(i).neighbors.get(j));
                    }
                } else {
                    continue;
                }
            }
            currentList = next;
        }
        return visited.get(node);
    }
}