leetcode133

133. Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/

Idea

Perform bfs algorithm to traverse the whole graph and get all the nodes firstly, and then copy the nodes and construct the mapping from original nodes to new nodes. Finally, copy the edges (neighbors) via the mapping.

Code

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        root = node
        if node is None:
            return None
        
        # bfs traverse the graph
        nodes = self.getNodes(root)
        
        # copy the nodes
        map = {}
        for node in nodes:
            map[node] = UndirectedGraphNode(node.label)
        
        # copy the edges
        for node in nodes:
            for n in node.neighbors:
                map[node].neighbors.append(map[n])
                
        return map[root]
        
        
    def getNodes(self, node):
        que = [node]
        visited = set()
        visited.add(node)
        while que:
            h = que.pop(0)
            for n in h.neighbors:
                if not (n in visited):
                    que.append(n)
                    visited.add(n)
        return list(visited)