Clone Graph

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 #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. 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.        1
  2.       / \
  3.      /   \
  4.     0 --- 2
  5.          / \
  6.          \_/

Solution:

  1. /**
  2.  * Definition for undirected graph.
  3.  * class UndirectedGraphNode {
  4.  *     int label;
  5.  *     List<UndirectedGraphNode> neighbors;
  6.  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
  7.  * };
  8.  */
  9. public class Solution {
  10.   public UndirectedGraphNode cloneGraph(UndirectedGraphNode root) {
  11.     if (root == null) return null;
  13.     // use a map to save cloned nodes
  14.     Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
  16.     // clone the root
  17.     map.put(root, new UndirectedGraphNode(root.label));
  19.     helper(root, map);
  21.     return map.get(root);
  22.   }
  24.   void helper(UndirectedGraphNode root, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
  25.     for (UndirectedGraphNode neighbor : root.neighbors) {
  26.       if (!map.containsKey(neighbor)) {
  27.         map.put(neighbor, new UndirectedGraphNode(neighbor.label));
  28.         helper(neighbor, map);
  29.       }
  31.       map.get(root).neighbors.add(map.get(neighbor));
  32.     }
  33.   }
  34. }