Simple 1 Pass Java DFS Solution, Very Readable and Easy to Understand, ~14 lines of code


  • 0
    S
    /**
     * Definition for undirected graph.
     * class UndirectedGraphNode {
     *     int label;
     *     List<UndirectedGraphNode> neighbors;
     *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
     * };
     */
    public class Solution {
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            HashSet<UndirectedGraphNode> set = new HashSet<>();
            DFS(node, set);
            return map.get(node);
        }
        
        // while doing DFS put the current node into map if it doesn't exist and after recursive call on neighbor nodes, you know the neighbor nodes exist in map, so create the neighbor edges
        public void DFS(UndirectedGraphNode node, HashSet<UndirectedGraphNode> visited) {
            if(node == null || visited.contains(node)) 
                return;
            
            visited.add(node);
            
            if(!map.containsKey(node)){
                map.put(node, new UndirectedGraphNode(node.label));
            }
            
            for(UndirectedGraphNode n : node.neighbors) {
                DFS(n, visited);
                map.get(node).neighbors.add(map.get(n));
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.