#!/user/bin/env python3

# coding=utf-8

"""

@project : algorithmPython

@ide : PyCharm

@file : cloneGraph

@author : illusion

@desc : 133. 克隆图 https://leetcode-cn.com/problems/clone-graph/

@create : 2021/6/5

"""

# 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 node is None:

return None

visited = {}

return self.dfs(node, visited)

def dfs(self, node: 'Node', visited):

if node in visited:

return visited[node]

new_node = Node(val=node.val)

visited[node] = new_node

for neighbor in node.neighbors:

new_node.neighbors.append(self.dfs(neighbor, visited))

return new_node