137. Clone Graph

Description

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

You need to return a deep copied graph, which has the same structure as the original graph, and any changes to the new graph will not have any effect on the original graph.

You need return the node with the same label as the input node.

Clarification

How we serialize an undirected graph: http://www.lintcode.com/help/graph/

Example

Example1

Input:

{1,2,4#2,1,4#4,1,2}

Output:

{1,2,4#2,1,4#4,1,2}

Explanation:

1------2 

\        | 

 \      | 

  \    | 

    \  | 

      4 

思路：

（并看不懂，等后续补充）使用宽度优先搜索 BFS 的版本。

第一步：找到所有的点

第二步：复制所有的点，将映射关系存起来

第三步：找到所有的边，复制每一条边

代码：