Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.

Second node is labeled as 1. Connect node 1 to node 2.

Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1

      / \

     /   \

    0 --- 2

         / \

         \_/

/**

 * Definition for undirected graph.

 * class UndirectedGraphNode {

 *     int label;

 *     List<UndirectedGraphNode> neighbors;

 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

 * };

 */

public class Solution {

    //dfs

    Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        if(node==null) return null;

        //copy graph(deep copy), hashmap

        map.put(node, new UndirectedGraphNode(node.label));

        helper(node);

        return map.get(node);

    }

    void helper(UndirectedGraphNode node){

        for(int i = 0; i< node.neighbors.size(); i++){

            UndirectedGraphNode neighbor = node.neighbors.get(i);

            if(!map.containsKey(neighbor)){// not visited

                UndirectedGraphNode newNode = new UndirectedGraphNode(neighbor.label);

                map.put(neighbor, newNode);//visited

                helper(neighbor);//why put helper here: where put stack where to recursive(update 1)

            }

            map.get(node).neighbors.add(map.get(neighbor)); //set the link of neighbors

        }

    }

}

/**

 * Definition for undirected graph.

 * class UndirectedGraphNode {

 *     int label;

 *     List<UndirectedGraphNode> neighbors;

 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

 * };

 */

public class Solution {

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        if(node==null) return null;

        //bfs

        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();

        queue.offer(node);

        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

        map.put(node,newNode);

        while(!queue.isEmpty()){

            UndirectedGraphNode cur = queue.poll();//pop

            for(int i = 0; i<cur.neighbors.size(); i++){

                UndirectedGraphNode neighbor = cur.neighbors.get(i);

                if(!map.containsKey(neighbor)){

                    queue.offer(neighbor);

                    newNode = new UndirectedGraphNode(neighbor.label);

                    map.put(neighbor, newNode);

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

                }

                //if contains the key

                else map.get(cur).neighbors.add(map.get(neighbor));

            }

        }

        return map.get(node);

    }

}

/**

 * Definition for undirected graph.

 * class UndirectedGraphNode {

 *     int label;

 *     List<UndirectedGraphNode> neighbors;

 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }

 * };

 */

public class Solution {

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

        if(node == null) return null;

        //dfs, if not visited, visited it and set it to visited, stack

        LinkedList<UndirectedGraphNode> stack = new LinkedList<>();//add first

        stack.push(node);

        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();

        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);

        map.put(node, newNode);

        while(!stack.isEmpty()){

            UndirectedGraphNode cur = stack.pop();//pop

            for(int i = 0; i<cur.neighbors.size(); i++){

                UndirectedGraphNode neighbor = cur.neighbors.get(i);//neighbor of current

                if(!map.containsKey(neighbor)){//put neighbor into hashmap (visited)

                    newNode = new UndirectedGraphNode(neighbor.label);//copy neighbors

                    map.put(neighbor, newNode);

                    stack.push(neighbor);

                }

                //set the link of neighbors

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

            }

        }

        return map.get(node);

    }

}

// relationship in hashmap

// key,             value

// cur,             map.get(cur)

// cur.neighbors,   newNode/ map.get(eighbor)