Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Solution:
Time: O(EV)
/**
* 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) {
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
Deque<UndirectedGraphNode> queue = new ArrayDeque<>();
Set<UndirectedGraphNode> visited = new HashSet<>();
queue.offer(node);
while (!queue.isEmpty()) {
UndirectedGraphNode curr = queue.poll();
if (visited.add(curr)) {
if (!map.containsKey(curr)) {
UndirectedGraphNode copy = new UndirectedGraphNode(curr.label);
map.put(curr, copy);
}
UndirectedGraphNode copy = map.get(curr);
for (UndirectedGraphNode nei : curr.neighbors) {
UndirectedGraphNode neiCopy = map.getOrDefault(nei, new UndirectedGraphNode(nei.label));
copy.neighbors.add(neiCopy);
map.put(nei, neiCopy);
queue.offer(nei);
}
}
}
return map.get(node);
}
}