|
7 | 7 | importjava.util.Map; |
8 | 8 | importjava.util.Queue; |
9 | 9 |
|
10 | | -/** |
11 | | - * 133. Clone Graph |
12 | | -
|
13 | | - Clone an undirected graph. |
14 | | - Each node in the graph contains a label and a list of its neighbors. |
15 | | -
|
16 | | -
|
17 | | - OJ's undirected graph serialization: |
18 | | - Nodes are labeled uniquely. |
19 | | -
|
20 | | - We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. |
21 | | - As an example, consider the serialized graph {0,1,2#1,2#2,2}. |
22 | | -
|
23 | | - The graph has a total of three nodes, and therefore contains three parts as separated by #. |
24 | | -
|
25 | | - First node is labeled as 0. Connect node 0 to both nodes 1 and 2. |
26 | | - Second node is labeled as 1. Connect node 1 to node 2. |
27 | | - Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. |
28 | | - Visually, the graph looks like the following: |
29 | | -
|
30 | | - 1 |
31 | | - / \ |
32 | | - / \ |
33 | | - 0 --- 2 |
34 | | - / \ |
35 | | - \_/ |
36 | | -
|
37 | | - */ |
38 | 10 | publicclass_133 { |
39 | 11 |
|
40 | | -publicstaticclassSolution1 { |
41 | | -publicUndirectedGraphNodecloneGraph(UndirectedGraphNodenode) { |
42 | | -if (node ==null) { |
43 | | -returnnode; |
44 | | - } |
45 | | - |
46 | | -Map<Integer,UndirectedGraphNode>map =newHashMap(); |
47 | | -Queue<UndirectedGraphNode>queue =newLinkedList(); |
48 | | -UndirectedGraphNoderoot =newUndirectedGraphNode(node.label); |
49 | | -map.put(root.label,root); |
50 | | -queue.offer(node); |
51 | | -//remember to offer the original input node into the queue which contains all the information |
52 | | -while (!queue.isEmpty()) { |
53 | | -UndirectedGraphNodecurr =queue.poll(); |
54 | | -for (UndirectedGraphNodeeachNode :curr.neighbors) { |
55 | | -if (!map.containsKey(eachNode.label)) { |
56 | | -map.put(eachNode.label,newUndirectedGraphNode(eachNode.label)); |
57 | | -queue.offer(eachNode); |
58 | | - } |
59 | | -map.get(curr.label).neighbors.add(map.get(eachNode.label)); |
| 12 | +publicstaticclassSolution1 { |
| 13 | +publicUndirectedGraphNodecloneGraph(UndirectedGraphNodenode) { |
| 14 | +if (node ==null) { |
| 15 | +returnnode; |
| 16 | + } |
| 17 | + |
| 18 | +Map<Integer,UndirectedGraphNode>map =newHashMap(); |
| 19 | +Queue<UndirectedGraphNode>queue =newLinkedList(); |
| 20 | +UndirectedGraphNoderoot =newUndirectedGraphNode(node.val); |
| 21 | +map.put(root.val,root); |
| 22 | +queue.offer(node); |
| 23 | +//remember to offer the original input node into the queue which contains all the information |
| 24 | +while (!queue.isEmpty()) { |
| 25 | +UndirectedGraphNodecurr =queue.poll(); |
| 26 | +for (UndirectedGraphNodeeachNode :curr.neighbors) { |
| 27 | +if (!map.containsKey(eachNode.val)) { |
| 28 | +map.put(eachNode.val,newUndirectedGraphNode(eachNode.val)); |
| 29 | +queue.offer(eachNode); |
| 30 | + } |
| 31 | +map.get(curr.val).neighbors.add(map.get(eachNode.val)); |
| 32 | + } |
| 33 | + } |
| 34 | +returnroot; |
60 | 35 | } |
61 | | - } |
62 | | -returnroot; |
63 | 36 | } |
64 | | - } |
65 | 37 | } |