solved "Clone Graph" on LeetCode http://oj.leetcode.com/problems/clone-graph/

CloneGraph.java

// class UndirectedGraphNode {
//     int label;
//     ArrayList<UndirectedGraphNode> neighbors;
//     UndirectedGraphNode(int x) {
//         label = x;
//         neighbors = new ArrayList<UndirectedGraphNode>();
//     }
// }

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) return null;
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        map.put(node, newNode);

        cloneVerticesByDFS(node, newNode);
        return newNode;
    }

    public void cloneVerticesByDFS(UndirectedGraphNode node, 
                                    UndirectedGraphNode newNode) {
        for (UndirectedGraphNode neighbor : node.neighbors) {
            if (map.containsKey(neighbor)) {
                newNode.neighbors.add(map.get(neighbor));
            }
            else {
                UndirectedGraphNode newNeighbor = 
                    new UndirectedGraphNode(neighbor.label);
                newNode.neighbors.add(newNeighbor);
                map.put(neighbor, newNeighbor);
                cloneVerticesByDFS(neighbor, newNeighbor);
            }
        }
    }

    private Map<UndirectedGraphNode, UndirectedGraphNode> map;
}