import collections class undirectedgraphnode def initself label self label label self neighbors def shallowcopyself return undirectedgraphnodeself label def addneighborself node self neighbors appendnode def clonegraph1node if not node return none nodecopy node shallowcopy dic node nodecopy queue collections dequenode while queue node queue popleft for neighbor in node neighbors if neighbor not in dic neighbor is not visited neighborcopy neighbor shallowcopy dicneighbor neighborcopy dicnode addneighborneighborcopy queue appendneighbor else dicnode addneighbordicneighbor return nodecopy def clonegraph2node if not node return none nodecopy node shallowcopy dic node nodecopy stack node while stack node stack pop for neighbor in node neighbors if neighbor not in dic neighborcopy neighbor shallowcopy dicneighbor neighborcopy dicnode addneighborneighborcopy stack appendneighbor else dicnode addneighbordicneighbor return nodecopy def clonegraphnode if not node return none nodecopy node shallowcopy dic node nodecopy dfsnode dic return nodecopy def dfsnode dic for neighbor in node neighbors if neighbor not in dic neighborcopy neighbor shallowcopy dicneighbor neighborcopy dicnode addneighborneighborcopy dfsneighbor dic else dicnode addneighbordicneighbor 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 _ a node in an undirected graph contains a label and a list of neighbouring nodes initially empty return a shallow copy of this node ignoring any neighbors adds a new neighbor returns a new graph as seen from the given node using a breadth first search bfs neighbor is not visited returns a new graph as seen from the given node using an iterative depth first search dfs returns a new graph as seen from the given node using a recursive depth first search dfs clones a graph using a recursive depth first search stores the clones in the dictionary keyed by the original nodes
r
import collections


class UndirectedGraphNode:
    

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

    def shallow_copy(self):
        
        return UndirectedGraphNode(self.label)

    def add_neighbor(self, node):
        
        self.neighbors.append(node)


def clone_graph1(node):
    
    if not node:
        return None
    node_copy = node.shallow_copy()
    dic = {node: node_copy}
    queue = collections.deque([node])
    while queue:
        node = queue.popleft()
        for neighbor in node.neighbors:
            if neighbor not in dic:  
                neighbor_copy = neighbor.shallow_copy()
                dic[neighbor] = neighbor_copy
                dic[node].add_neighbor(neighbor_copy)
                queue.append(neighbor)
            else:
                dic[node].add_neighbor(dic[neighbor])
    return node_copy


def clone_graph2(node):
    
    if not node:
        return None
    node_copy = node.shallow_copy()
    dic = {node: node_copy}
    stack = [node]
    while stack:
        node = stack.pop()
        for neighbor in node.neighbors:
            if neighbor not in dic:
                neighbor_copy = neighbor.shallow_copy()
                dic[neighbor] = neighbor_copy
                dic[node].add_neighbor(neighbor_copy)
                stack.append(neighbor)
            else:
                dic[node].add_neighbor(dic[neighbor])
    return node_copy


def clone_graph(node):
    
    if not node:
        return None
    node_copy = node.shallow_copy()
    dic = {node: node_copy}
    dfs(node, dic)
    return node_copy


def dfs(node, dic):
    
    for neighbor in node.neighbors:
        if neighbor not in dic:
            neighbor_copy = neighbor.shallow_copy()
            dic[neighbor] = neighbor_copy
            dic[node].add_neighbor(neighbor_copy)
            dfs(neighbor, dic)
        else:
            dic[node].add_neighbor(dic[neighbor])