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
33
34
35
36
37
38 | /**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes =
new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
mapClone(node, cloneNodes);
UndirectedGraphNode[] allNodes = cloneNodes.keySet()
.toArray(new UndirectedGraphNode[cloneNodes.size()]);
for (int i = 0; i < allNodes.length; i++){
UndirectedGraphNode copyNode = cloneNodes.get(allNodes[i]);
List<UndirectedGraphNode> neighbors = allNodes[i].neighbors;
for (int j = 0; j < neighbors.size(); j++){
copyNode.neighbors.add(cloneNodes.get(neighbors.get(j)));
}
}
return cloneNodes.get(node);
}
public void mapClone(UndirectedGraphNode node,
HashMap<UndirectedGraphNode, UndirectedGraphNode> cloneNodes){
if (cloneNodes.containsKey(node)) return;
cloneNodes.put(node, new UndirectedGraphNode(node.label));
List<UndirectedGraphNode> neighbors = node.neighbors;
for (int i = 0; i < neighbors.size(); i++){
mapClone(neighbors.get(i), cloneNodes);
}
}
}
|
No comments:
Post a Comment