import java.util.ArrayList;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.Queue;

public class P0133CloneGraph {

public class Node {

int val;

ArrayList<Node> neighbors;

public Node(int val, ArrayList<Node> nei) {

this.val = val;

this.neighbors = nei;

}

}

HashMap<Node, Node> graphMap = new HashMap<>();// 存原始的和copy的节点

public Node cloneGraph(Node node) {

if (node == null)

return null;// 节点不存在 指针指向null

if (graphMap.containsKey(node)) {

return graphMap.get(node);// 节点如果存在与map中，直接取出来用。避免重复copy

}

Node newHead = new Node(node.val, new ArrayList<>());// map里没有的节点需要开出新的Node来

graphMap.put(node, newHead);// 将目前已经克隆出的节点添加到map里，Key是原始节点，Value是对应的Copy节点

for (Node nei : node.neighbors) {// 对节点的邻居们进行处理。也要check map里是否存在邻节点，避免重复操作

newHead.neighbors.add(cloneGraph(nei));

// 如果节点之前copy过，直接返回map里取出来的值

}

return newHead;

}

HashMap<Node, Node> map = new HashMap<>();

public Node cloneGraph2(Node node) {// 这个模版更好理解

if (node == null)

return null;

return dfs(node);// 题目给出起点就是一个节点，所以返回clone的起点即可。

}

Node dfs(Node node) {

// node节点已经被访问过了,直接从哈希表hash中取出对应的克隆节点返回。

if (map.containsKey(node))

return map.get(node);

Node clone = new Node(node.val, new ArrayList<>()); // 克隆节点

map.put(node, clone); // 建立源节点到克隆节点的映射

for (Node ver : node.neighbors) // 克隆边

{

clone.neighbors.add(dfs(ver));// 递归的返回值直接添加到list里面

}

return clone;

}

public Node cloneGraphBFS(Node node) {// BFS做法

if (node == null)

return null;

HashMap<Node, Node> map = new HashMap<>();

Node cloneNode = new Node(node.val, new ArrayList<>());// 克隆节点，邻居先不关注

Queue<Node> queue = new LinkedList<>();

map.put(node, cloneNode);

queue.offer(node);// 第一个节点肯定要添加进去

while (!queue.isEmpty()) {

Node popE = queue.poll();

// 查看邻居节点

for (Node nei : popE.neighbors) {

if (!map.containsKey(nei)) {

Node newNode = new Node(nei.val, new ArrayList<>());

map.put(nei, newNode);

queue.offer(nei);

}

map.get(popE).neighbors.add(map.get(nei));// 必须用map取出对应的克隆节点

}

}

return cloneNode;

}

public Node cloneGraph1(Node node) {

if (node == null)

return null;

HashMap<Node, Node> map = new HashMap<>();

Node newNode = new Node(node.val, new ArrayList<>());// 只添加value，不添加nei，但先初始化为空

map.put(node, newNode);

//  已经复制过的，但neighbor还没添加

Queue<Node> queue = new LinkedList<>();// Queue为接口，linkedlist是类型；

queue.offer(node);

while (!queue.isEmpty()) {// 队列循环标准格式

Node cur = queue.poll();// 将队列中的元素取出来进行下一步操作

for (Node nei : cur.neighbors) {// 对当前poll出来元素的邻居们进行添加

if (map.containsKey(nei)) {

map.get(cur).neighbors.add(map.get(nei));

} else {

Node newNei = new Node(nei.val, new ArrayList<>());

map.get(cur).neighbors.add(newNei);

map.put(nei, newNei);

queue.offer(nei);

}

}

}

return newNode;

}

}

// Time Complexity: O(V + E)

// Space Complexity: O(V). Both Recursion Stack and HashMap will take O(V) space

// V = Number of nodes. E = Number of edges in the graph.

/*

* 题目给出的仅有一个开始起点。我们需要做的是通过这个节点把整个图还原做copy。所以先copy当前节点，然后取访问当前节点的邻居，

* 如果它的邻居已经做过copy，则直接使用，如果不存在map里，则做copy并mark在map里，避免重复copy。比如我们已经做过节点1的copy，

* 访问到节点2的时候，发现它的邻居是1，如果没有map的辅助，会重新在创建一个新的节点1.但因为借助于map，我们知道节点1已经被copy过，

* 所以直接使用就好，把这个节点添加到节点2的邻居节点里。

*/