Demo entry 6635014

133. Clone Graph

   

Submitted by Jason on Aug 16, 2017 at 02:22
Language: Java. Code size: 2.1 kB.

/**
 * 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; 
        }
        
        Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        HashSet<UndirectedGraphNode> set = new HashSet<>();
        // 3, 4, 4
        // 3-4', 3-4''
        //set2 is used to avoid 3 connect to 4''
        HashSet<UndirectedGraphNode> set2 = new HashSet<>();
        
        UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
        map.put(node, newNode);
        q.offer(node);
        
        while (!q.isEmpty()) {
            UndirectedGraphNode temp = q.poll();
            if (!set.contains(temp)) {
                set.add(temp);
                UndirectedGraphNode find = map.get(temp);
                for (UndirectedGraphNode neighbor: temp.neighbors) {
                    
                    if (neighbor != temp && !set2.contains(neighbor)) {
                        UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label);
                        map.put(neighbor, newNeighbor);
                        set2.add(neighbor);
                        find.neighbors.add(newNeighbor);
                        q.offer(neighbor);
                    } else if (set2.contains(neighbor)) {
                        // handle this case: 3,4,4
                        find.neighbors.add(map.get(neighbor));
                    } else {
                        // handle this case: 2,2
                        find.neighbors.add(find);
                    }

                }
            }
 
        }
        
        return newNode;
    }
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).