133. Clone Graph

My last AC submission was in May 2022, almost one year has passed and fk my memory about this problem has gone too. 🥲

My first intuition was nearly correct (DFS and clone along the way), however, I messed up with some details. Then I came up with the first approach below… Not fast but quite easy to understand.

First Approach

General Idea

The complicated part about this problem is how do we avoid going into a loop and make sure we cover every edge in the cloned graph.

A wrong way to do this is to use a seen_node set to avoid visiting the same node, but this way, we lose edges(note we use two directional edges to represent a undirected edge, so an undirected edge between A and B means A has B in its neighbors and B has A in its neighbors)

So the idea of separating the processing of nodes and edges came up, we visit the existing graph, clone the nodes along the way(with the help of hashmap) and record all edges, then we use another step to connect the cloned nodes.

Algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        m={}
        q=collections.deque([node])
        edges=set()
        while q:
            n=q.popleft()
            m[n]=Node(n.val)
            for neighbor in n.neighbors:
                edge=(n,neighbor)
                if edge not in edges:
                    edges.add(edge)
                    q.append(neighbor)

        for s,d in edges:
            m[s].neighbors.append(m[d])
        return m[node]

BFS to visit the graph, but we use edges as a indicator of repeating visit, instead of nodes, so in the end we have all the edges available in set edges, and obviously, we clone the nodes along the way and save in m.

Then we simply connect the cloned nodes using edges

This is kind of slow (beats ~40%) but I think it is quite intuitive(and should be able to pass an interview).

Second Approach

Idea

The idea is taken form the official solution but with some tweaks for easier coding.

DFS and clone the graph along the way.

It’s the same here, how do we avoid going into a infinite loop? Use the cloned node map as an indicator!

We define a clone function and this will first check if the given node has been cloned already, if so, simply return.

If the given node is not cloned, we clone it and add it to the map first, otherwise we will be stuck in recursion. Then we clone every neighbor, and add the cloned node to the neighbors list.

Algorithm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        m={}
        def clone(node):
            if node in m:
                return m[node]
            cn=Node(node.val)
            m[node]=cn
            for neighbor in node.neighbors:
                cn.neighbors.append(clone(neighbor))
            return cn
        return clone(node)

Yo!! 1