Question: https://oj.leetcode.com/problems/clone-graph/
Question Name: Clone Graph
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | # 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): # Empty graph if node == None: return # Do the work in two rounds. In the first round, we clone all the # new nodes only with label. And let their neighbors array empty. # In the second round, we will assign the neighbors of cloned # node with the reference to new cloned ones. # Clone nodes only with label cloned = {} currentLayer = [node] while len(currentLayer) != 0: nextLayer = [] for toClone in currentLayer: if toClone in cloned: continue temp = UndirectedGraphNode(toClone.label) nextLayer.extend(toClone.neighbors) cloned[toClone] = temp currentLayer = nextLayer # Assign the neighbors of new cloned nodes. for oldNode in cloned: newNode = cloned[oldNode] newNode.neighbors = [cloned[neighbor] for neighbor in oldNode.neighbors] return cloned[node] |
Both BFS and DFS are given. Leetcode is not very stable recently. The new UIs never work right…