Clone Graph
Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Tags: Graph
Try It!
Discussion
Video
Solution
"""
# 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 = []
visited = {}
stack.append(node)
visited[node.val] = Node(node.val)
while stack:
top = stack.pop()
for neighbor in top.neighbors:
if neighbor.val not in visited:
stack.append(neighbor)
visited[neighbor.val] = Node(neighbor.val)
visited[top.val].neighbors.append(visited[neighbor.val])
return visited[node.val]
DFS recursive solution
"""
# 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
visited = {}
return self.dfs(node, visited)
def dfs(self, node, visited):
if node.val in visited:
return visited[node.val]
copy = Node(node.val)
visited[node.val] = copy
for nei in node.neighbors:
copy.neighbors.append(self.dfs(nei, visited))
return copy