1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 13, 2015
4+ Problem: Clone Graph
5+ Difficulty: Medium
6+ Source: http://oj.leetcode.com/problems/clone-graph/
7+ Notes:
8+ Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
9+
10+ OJ's undirected graph serialization:
11+ Nodes are labeled from 0 to N - 1, where N is the total nodes in the graph.
12+ We use # as a separator for each node, and , as a separator for each neighbor of the node.
13+ As an example, consider the serialized graph {1,2#2#2}.
14+ The graph has a total of three nodes, and therefore contains three parts as separated by #.
15+ Connect node 0 to both nodes 1 and 2.
16+ Connect node 1 to node 2.
17+ Connect node 2 to node 2 (itself), thus forming a self-cycle.
18+ Visually, the graph looks like the following:
19+
20+ 1
21+ / \
22+ / \
23+ 0 --- 2
24+ / \
25+ \_/
26+
27+ Solution: 1. DFS. 2. BFS.
28+ */
29+
30+ /**
31+ * Definition for undirected graph.
32+ * class UndirectedGraphNode {
33+ * int label;
34+ * List<UndirectedGraphNode> neighbors;
35+ * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
36+ * };
37+ */
38+ public class Solution {
39+ public UndirectedGraphNode cloneGraph_1 (UndirectedGraphNode node ) {
40+ HashMap <UndirectedGraphNode ,UndirectedGraphNode >map =new HashMap <UndirectedGraphNode ,UndirectedGraphNode >();
41+ return cloneGraphRe (node ,map );
42+ }
43+ public UndirectedGraphNode cloneGraphRe (UndirectedGraphNode node ,HashMap <UndirectedGraphNode ,UndirectedGraphNode >map ) {
44+ if (node ==null )return null ;
45+ if (map .containsKey (node ) ==true ) {
46+ return map .get (node );
47+ }
48+ UndirectedGraphNode newnode =new UndirectedGraphNode (node .label );
49+ map .put (node ,newnode );
50+ for (UndirectedGraphNode cur :node .neighbors ) {
51+ newnode .neighbors .add (cloneGraphRe (cur ,map ));
52+ }
53+ return newnode ;
54+ }
55+ public UndirectedGraphNode cloneGraph (UndirectedGraphNode node ) {
56+ HashMap <UndirectedGraphNode ,UndirectedGraphNode >map =new HashMap <UndirectedGraphNode ,UndirectedGraphNode >();
57+ Queue <UndirectedGraphNode >queue =new LinkedList <UndirectedGraphNode >();
58+ if (node ==null )return null ;
59+ queue .offer (node );
60+ map .put (node ,new UndirectedGraphNode (node .label ));
61+ while (queue .isEmpty () ==false ) {
62+ UndirectedGraphNode cur =queue .poll ();
63+ for (UndirectedGraphNode neighbor :cur .neighbors ) {
64+ if (map .containsKey (neighbor ) ==false ) {
65+ UndirectedGraphNode newnode =new UndirectedGraphNode (neighbor .label );
66+ map .put (neighbor ,newnode );
67+ queue .offer (neighbor );
68+ }
69+ map .get (cur ).neighbors .add (map .get (neighbor ));
70+ }
71+ }
72+ return map .get (node );
73+ }
74+ }
