import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * created by zl on 2019/5/11 10:38
 */
public class medium_133_clonegraph
{
    class Node {
        public int val;
        public List<Node> neighbors;

        public Node() {}

        public Node(int _val,List<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    };
    public Node cloneGraph(Node node)
    {
        Map<Integer,Node> map = new HashMap();
        Node n = new Node(node.val, null);
        map.put(node.val,n);
        n.neighbors = copy(node, map);
        return n;
    }

    private List<Node> copy(Node node,Map<Integer,Node> map)
    {
        List<Node> list = new ArrayList<>();
        for(Node n : node.neighbors)
        {
            if(map.containsKey(n.val))
            {//判断该节点是否已经创建了
                list.add(map.get(n.val));
            }else
            {
                Node nn = new Node(n.val, null);//节点未创建，创建并拷贝nei***ors
                list.add(nn);
                map.put(n.val, nn);
                nn.neighbors = copy(n, map);
            }
        }
        return list;
    }

}