-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCloneGraph.java
More file actions
36 lines (32 loc) · 1.33 KB
/
Copy pathCloneGraph.java
File metadata and controls
36 lines (32 loc) · 1.33 KB
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
/**
* 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;
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
Queue<UndirectedGraphNode> q = new LinkedList<>();
UndirectedGraphNode nodeCopy = new UndirectedGraphNode(node.label);
map.put(node, nodeCopy);
q.add(node);
while (!q.isEmpty()) {
UndirectedGraphNode n = q.remove();
for (UndirectedGraphNode neighbor : n.neighbors) {
if (map.containsKey(neighbor)) {
map.get(n).neighbors.add(map.get(neighbor));
} else {
UndirectedGraphNode neighborCopy = new UndirectedGraphNode(neighbor.label);
map.get(n).neighbors.add(neighborCopy);
map.put(neighbor, neighborCopy);
q.add(neighbor);
}
}
}
return nodeCopy;
}
}