133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

Graph is an UndirectedGraphNode.

class UndirectedGraphNode:
    def __init__(self, x):
        self.label = x
        self.neighbors = []

Solution: HashMap & DFS

class Solution:
    def cloneGraph(self, graph):
        """
        :type graph: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if not graph:
            return graph

        cloned = dict()

        def dfs(node):
            if node in cloned:
                return cloned[node]
            clone = UndirectedGraphNode(node.label)
            cloned[node] = clone
            for neighbor in node.neighbors:
                clone.neighbors.append(dfs(neighbor))
            return clone

        dfs(graph)
        return cloned[graph]