/**
1.  可以按dfs的方式遍历整个图, new出相同val的节点即可, 这题是无向图, 所以需要一个Map来记录经过的点并去重
1.1 搜索顺序: 因为所有node.val不同, 所以如果已经处理过的node 直接返回; 未处理过的node copy后递归处理neighbors;
1.2 搜索状态: local: cur_node | global: ready
1.3 剪枝: ~
*/

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }

    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
    public Node cloneGraph(Node node) {
        return cloneGraph(node, new HashMap<Integer, Node>());
    }

    public Node cloneGraph(Node node, Map<Integer, Node> ready){
        if (node == null) return null;

        Node mirror = ready.get(node.val);
        if (mirror != null) return mirror;
        mirror = new Node(node.val);
        ready.put(node.val, mirror);

        for (int i = 0 ; i < node.neighbors.size(); i++){
            Node next = node.neighbors.get(i);
            mirror.neighbors.add(cloneGraph(next, ready));
        }
        return mirror;
    }

}