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);
    }
}