Clone Graph (DFS)

LeetCode 133

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
"""
DFS-Iterative-Stack
"""
class Solution:
    def cloneGraph(self, node):
        if not node:
            return node 
        stack = [node]
        visited = {node:UndirectedGraphNode(node.label)}
        head = visited[node]      
        while stack:
            node = stack.pop()
            for ns in node.neighbors:
                if ns not in visited:
                    stack.append(ns)
                    visited[ns] = UndirectedGraphNode(ns.label)
                visited[node].neighbors.append(visited[ns])
        return head