LeetCode: Clone Graph

## https://code.dennyzhang.com/clone-graph
## Basic Ideas: Use a hashmap
##              For each new node, create one.
##              Scan its neighbors, if found new nodes. Create them. And update mapping
##              Update children
##
## Complexity: Time O(n^2), Space O(n).
##
# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if node is None: return None
        d = {}
        self.DFSClone(node, d)
        return d[node][0]

    def DFSClone(self, node, d):
        if node is None: return None
        if node not in d:
            newNode = UndirectedGraphNode(node.label)
            d[node] = (newNode, False)
        (newNode, has_finished) = d[node]
        if has_finished is True:
            return newNode

        # mark as DONE to avoid duplicate visits
        d[node] = (newNode, True)
        for neighbor in node.neighbors:
            newNeighbor = self.DFSClone(neighbor, d)
            newNode.neighbors.append(newNeighbor)
        return newNode