javadfs twin clone


  • 0
    Y

    The idea is let every node have a twin. And we'll connect the twin together during dfs.
    Further improve: use Integer to be the key in Set and Map.

    private Set<UndirectedGraphNode> visited = new HashSet<>();
    private Map<UndirectedGraphNode, UndirectedGraphNode> bundle = new HashMap<>();
        
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if (null == node) return null;
            dfs(node);
            return bundle.get(node);
        }
    
        private UndirectedGraphNode getTwin(UndirectedGraphNode v) {
            UndirectedGraphNode twin = null;
            if (!bundle.containsKey(v))  {
                twin = new UndirectedGraphNode(v.label);
                bundle.put(v, twin);
            }
            else twin = bundle.get(v);
            
            return twin;
        }
        
        private void dfs(UndirectedGraphNode v) {
            visited.add(v);
            
            UndirectedGraphNode vTwin = getTwin(v);
            for (UndirectedGraphNode u : v.neighbors) {
                vTwin.neighbors.add(getTwin(u));
                if (!visited.contains(u)) dfs(u);
            } 
        }
    
    

Log in to reply
 

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