// Path: src/commons/datastructures/UndirectedGraphNode.java
// public class UndirectedGraphNode {
//     public int label;
//     public List<UndirectedGraphNode> neighbors;
//     public  UndirectedGraphNode(int x) {
//         label = x;
//         neighbors = new ArrayList<UndirectedGraphNode>();
//     }
// }


import commons.datastructures.UndirectedGraphNode;
import java.util.HashMap;
import java.util.Map;
package CloneGraph;



/**
 * User: Danyang
 * Date: 1/27/2015
 * Time: 23:55
 * Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node==null)
            return null;
        Map<UndirectedGraphNode, UndirectedGraphNode> cloned = new HashMap<>();
        dfs(node, cloned);
        return cloned.get(node);
    }

// Path: src/commons/datastructures/UndirectedGraphNode.java
// public class UndirectedGraphNode {
//     public int label;
//     public List<UndirectedGraphNode> neighbors;
//     public  UndirectedGraphNode(int x) {
//         label = x;
//         neighbors = new ArrayList<UndirectedGraphNode>();
//     }
// }


// Path: src/CloneGraph/Solution.java
import commons.datastructures.UndirectedGraphNode;
import java.util.HashMap;
import java.util.Map;

package CloneGraph;



/**
 * User: Danyang
 * Date: 1/27/2015
 * Time: 23:55
 * Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node==null)
            return null;
        Map<UndirectedGraphNode, UndirectedGraphNode> cloned = new HashMap<>();
        dfs(node, cloned);
        return cloned.get(node);
    }

    void dfs(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> cloned) {