Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

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

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        //map: map the original node to its clone
        //queue: for BFS
        Map<Node, Node> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();

        //add the first node to queue
        //give the fisrt node a clone in map, notice we can only 
        //--have an empty ArrayList for the neighbors in the clone
        queue.add(node);
        map.put(node, new Node(node.val, new ArrayList<>()));

        //BFS continues until all nodes in the original graph is processed,
        //--that is when queue is empty.
        while(!queue.isEmpty()) {
            //take the first node in the queue and process
            Node currNode = queue.poll();
            //iterate over all neighbors
            for (Node neighbor : currNode.neighbors) {
                //has this neighbor been given a clone?
                if(!map.containsKey(neighbor)) {
                    //no clone, give it a clone in map
                    //--and put it in queue for further process
                    map.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    queue.add(neighbor);
                }
                //connect the currNode's clone to neighbor's clone
                map.get(currNode).neighbors.add(map.get(neighbor)); //这里加的必须是map.get(neighbor)，
                //为什么不能是new Node(neighbor.val, new ArrayList<>())?
                //因为new出来的这个是another copy of neighbor，不是map里面neighbor对应的value。所以要从map里面拿！
            }
        }
        //return the clone of the first node, where is the start point of cloned graph.
        return map.get(node);
    }
}