Question

Formatted question description: https://leetcode.ca/all/133.html

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

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
         / \
         \_/

Note:
    The number of nodes will be between 1 and 100.
    The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
    Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
    You must return the copy of the given node as a reference to the cloned graph.


@tag-graph

Algorithm

In the recursive function, it is first to check if empty, and then to see whether the current node has been cloned,

if it exists in the HashMap, it will directly return to its mapping node.
Otherwise, clone the current node and create a mapping in HashMap, then traverse all neihbor nodes of the current node, call the recursive function and add it to the neighbors array of the cloned node.

Same idea of HashMap for BFS solution.

Code

Java

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Clone_Graph {

	/**
	 * Definition for undirected graph.
	 * class UndirectedGraphNode {
	 *     int label;
	 *     List<UndirectedGraphNode> neighbors;
	 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
	 * };
	 */
	public class Solution {
	    // from original node, to its copy
	    HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<>();

	    Set<UndirectedGraphNode> visited = new HashSet<>();

	    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {

	        if (node == null) {
	            return null;
	        }

	        // it can be done in either dfs or bfs
	        // I prefer bfs, less space cost
	        Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();

	        q.offer(node);

	        while (!q.isEmpty()) {

	            UndirectedGraphNode currentOriginal = q.poll();
	            UndirectedGraphNode currentCopy = getClonedNode(currentOriginal);

	            visited.add(currentOriginal);

	            for (UndirectedGraphNode nb: currentOriginal.neighbors) {

	                UndirectedGraphNode nbCopy = getClonedNode(nb);


	            	/*

	        		Input:
	        		{0,0,0}
	        		Output:
	        		{0,0,0,0,0}
	        		Expected:
	        		{0,0,0}

	            	*/
	                // @note: if add each other, then failed by above input
	                // 			so, should only add currentCopy's neighbors, and rest put in queue for next processing
	                currentCopy.neighbors.add(nbCopy);

	                // if (!visited.contains(nb)) {
	                if (!visited.contains(nb) && !q.contains(nb)) {
	                    q.offer(nb);
	                }

	            }
	        }

	        return hm.get(node);
	    }

	    private UndirectedGraphNode getClonedNode(UndirectedGraphNode original) {

	        UndirectedGraphNode originalCopy;

	        if (!hm.containsKey(original)) {

	            originalCopy = new UndirectedGraphNode(original.label);
	            hm.put(original, originalCopy); // as long as no mapping from original to its copy, add it
	        } else {
	            originalCopy = hm.get(original);
	        }

	        return originalCopy;
	    }
	}
}

// OJ: https://leetcode.com/problems/clone-graph/
// Time: O(N)
// Space: O(N)
class Solution {
    unordered_map<Node*, Node*> m;
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        if (m.count(node)) return m[node];
        auto cpy = new Node(node->val);
        m[node] = cpy;
        for (auto &n : node->neighbors) cpy->neighbors.push_back(cloneGraph(n));
        return cpy;
    }
};

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
  # @param node, a undirected graph node
  # @return a undirected graph node
  def cloneGraph(self, node):
    graph = {}
    visited = set()

    def dfs(node, visited, graph):
      if not node or node.label in visited:
        return
      visited |= {node.label}
      if node.label not in graph:
        graph[node.label] = UndirectedGraphNode(node.label)
      newNode = graph[node.label]

      for nbr in node.neighbors:
        if nbr.label not in graph:
          graph[nbr.label] = UndirectedGraphNode(nbr.label)
        newNode.neighbors.append(graph[nbr.label])
        dfs(nbr, visited, graph)
      return newNode

    return dfs(node, visited, graph)

133 - Clone Graph

Question

Algorithm

Code

All Problems

All Solutions