What can I say, I like graphs. This problem is from the archives, but I think especially from a pedagogical standpoint these “copy the data structure” (or usually I like, “print the data structure”) are terrific educational exercises.
The approach I took for this problem is the commented helper function. I think I need to review DFS/BFS and make sure I’m using the right number of node-marking (typically I’ve seen it formulated as a node being “marked” done or workset, rather than added to a set — that is more efficient generally.
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node is None:
return None
# We want to provide a function to get the
# "corresponding" node, allocating it if needed.
cor = {}
def getCor(u):
if u not in cor:
cor[u] = Node(u.val)
return cor[u]
workset = set([])
done = set([])
workset.add(node)
while len(workset) > 0:
n = workset.pop()
if n in done:
continue
m = getCor(n)
for u in n.neighbors:
v = getCor(u)
m.neighbors.append(v)
if u not in done:
if u not in workset:
workset.add(u)
done.add(n)
return getCor(node)
Notes
- All graph problems (rare) are collected here.