<reponame>Linchin/python_leetcode_git<filename>Q133-v3.py<gh_stars>0
"""
133
medium
clone graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
"""


# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []




class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':

        if not node:
            return None

        stack = [node]
        visited = {}

        new_graph = {}

        while stack:
            curr = stack.pop()
            visited[curr.val] = curr
            if curr.val not in new_graph:
                new_graph[curr.val] = Node(curr.val)
            for n in curr.neighbors:
                if n.val not in new_graph:
                    new_graph[n.val] = Node(n.val)
                if new_graph[n.val] not in new_graph[curr.val].neighbors:
                    new_graph[curr.val].neighbors.append(new_graph[n.val])
                if n.val not in visited:
                    stack.append(n)

        return new_graph[node.val]
































"""
133
medium
clone graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
"""


# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []




class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':

        if not node:
            return None

        stack = [node]
        visited = {}

        new_graph = {}

        while stack:
            curr = stack.pop()
            visited[curr.val] = curr
            if curr.val not in new_graph:
                new_graph[curr.val] = Node(curr.val)
            for n in curr.neighbors:
                if n.val not in new_graph:
                    new_graph[n.val] = Node(n.val)
                if new_graph[n.val] not in new_graph[curr.val].neighbors:
                    new_graph[curr.val].neighbors.append(new_graph[n.val])
                if n.val not in visited:
                    stack.append(n)

        return new_graph[node.val]
133 medium clone graph  Given a reference of a node in a connected undirected graph.  Return a deep copy (clone) of the graph.  Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. # Definition for a Node.