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 #.
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 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 __init__(self):
self.dict = {}
def cloneGraph(self, node):
# write your code here
if node is None:
return node
if node.label not in self.dict:
# if the node is not in dict, create the copy in dict first
n1 = UndirectedGraphNode(node.label)
self.dict[node.label] = n1
# append all the neighbors by using depth first search. It creates
# all the nodes first
neighbors = []
for i in node.neighbors:
neighbors.append(self.cloneGraph(i))
n1.neighbors = neighbors
return n1
else:
return self.dict[node.label]