110. Clone Graph

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */

import java.util.Hashtable;

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node==null) return null;
       
        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode> ();
        Hashtable<UndirectedGraphNode, UndirectedGraphNode> hashtable = new Hashtable<UndirectedGraphNode, UndirectedGraphNode> ();
       
        UndirectedGraphNode res = new UndirectedGraphNode(node.label);
        hashtable.put(node, res);
        queue.add(node);
       
        while (!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.remove();
            UndirectedGraphNode curclone = hashtable.get(cur);
           
            ArrayList<UndirectedGraphNode> neighbors = (ArrayList<UndirectedGraphNode>) cur.neighbors;
           
            for (int i=0; i<neighbors.size(); i++) {
                UndirectedGraphNode neighbor = neighbors.get(i);
                if (hashtable.containsKey(neighbor)) {
                    UndirectedGraphNode neighborclone = hashtable.get(neighbor);
                    curclone.neighbors.add(neighborclone);
                } else {
                    UndirectedGraphNode neighborclone = new UndirectedGraphNode(neighbor.label);
                    curclone.neighbors.add(neighborclone);
                    queue.add(neighbor);
                    hashtable.put(neighbor, neighborclone);
                }
            }
        }
       
        return res;
    }
}