package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode.com/problems/clone-graph/
 */
public class Problem133 {
    private static class UndirectedGraphNode {
        int label;
        List<UndirectedGraphNode> neighbors;

        UndirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<UndirectedGraphNode>();
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("UndirectedGraphNode [label=");
            builder.append(label);
            builder.append(", neighbors=");
            builder.append(neighbors);
            builder.append("]");
            return builder.toString();
        }
    };

    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return node;
        }
        UndirectedGraphNode copy = new UndirectedGraphNode(node.label);
        Set<Integer> marked = new HashSet<>();
        dfs(node, copy, marked);
        return copy;
    }
    
    private void dfs(UndirectedGraphNode source, UndirectedGraphNode copy, Set<Integer> marked) {
        marked.add(source.label);
        for (UndirectedGraphNode n : source.neighbors) {
            UndirectedGraphNode nCopy = new UndirectedGraphNode(n.label);
            copy.neighbors.add(nCopy);
            if (!marked.contains(n.label)) {
                UndirectedGraphNode nCopy = new UndirectedGraphNode(n.label);
                copy.neighbors.add(nCopy);
                dfs(n, nCopy, marked);
            }
        }
    }
    
    public static void main(String[] args) {
        Problem133 prob = new Problem133();
        
//        UndirectedGraphNode n0 = new UndirectedGraphNode(0);
//        UndirectedGraphNode n1 = new UndirectedGraphNode(1);
//        UndirectedGraphNode n2 = new UndirectedGraphNode(2);
//        
//        n0.neighbors.add(n1);
//        n0.neighbors.add(n2);
//        
//        n1.neighbors.add(n0);
//        n1.neighbors.add(n2);
//        
//        n2.neighbors.add(n0);
//        n2.neighbors.add(n1);
//        n2.neighbors.add(n2);
//        
//        UndirectedGraphNode cp0 = prob.cloneGraph(n0);
        
        UndirectedGraphNode n0 = new UndirectedGraphNode(0);
        n0.neighbors.add(n0);
        
        UndirectedGraphNode cp0 = prob.cloneGraph(n0);
        System.out.println(cp0.neighbors.get(0));
    }
}

@@ -36,24 +36,50 @@
 .ArrayList;%0A
+import java.util.HashMap;%0A
 import java.
@@ -111,24 +111,46 @@
 .util.List;%0A
+import java.util.Map;%0A
 import java.
@@ -987,32 +987,101 @@
 node;%0A        %7D%0A
+        Map%3CInteger, UndirectedGraphNode%3E copyMap = new HashMap%3C%3E();%0A
         Undirect
@@ -1128,32 +1128,71 @@
 de(node.label);%0A
+        copyMap.put(node.label, copy);%0A
         Set%3CInte
@@ -1244,32 +1244,41 @@
 de, copy, marked
+, copyMap
 );%0A        retur
@@ -1370,16 +1370,24 @@
 de copy,
+%0A       
  Set%3CInt
@@ -1398,16 +1398,59 @@
 %3E marked
+, Map%3CInteger, UndirectedGraphNode%3E copyMap
 ) %7B%0A    
@@ -1626,58 +1626,19 @@
     
-copy.neighbors.add(nCopy);%0A            if (!marked
+if (copyMap
 .con
@@ -1642,16 +1642,19 @@
 contains
+Key
 (n.label
@@ -1678,358 +1678,112 @@
     
-UndirectedGraphNode nCopy = new UndirectedGraphNode(n.label);%0A                copy.neighbors.add(nCopy);%0A                dfs(n, nCopy, marked);%0A            %7D%0A        %7D%0A    %7D%0A    %0A    public static void main(String%5B%5D args) %7B%0A        Problem133 prob = new Problem133();%0A        %0A//        UndirectedGraphNode n0 = new UndirectedGraphNode(0
+nCopy = copyMap.get(n.label);%0A            %7D else %7B%0A                copyMap.put(n.label, nCopy
 );%0A
-//
         
 Undi
@@ -1782,209 +1782,61 @@
     
-UndirectedGraphNode n1 = new UndirectedGraphNode(1);%0A//        UndirectedGraphNode n2 = new UndirectedGraphNode(2);%0A//        %0A//        n0.neighbors.add(n1);%0A//        n0.neighbors.add(n2
+    %7D%0A            copy.neighbors.add(nCopy
 );%0A
-//
         
 %0A// 
@@ -1835,356 +1835,106 @@
     
-%0A//
     
-    n1.neighbors.add(n0);%0A//        n1.neighbors.add(n2);%0A//        %0A//        n2.neighbors.add(n0);%0A//        n2.neighbors.add(n1);%0A//        n2.neighbors.add(n2);%0A//        %0A//        UndirectedGraphNode cp0 = prob.cloneGraph(n0);%0A        %0A        UndirectedGraphNode n0 = new UndirectedGraphNode(0);%0A        n0.neighbors.add(n0);%0A
+if (!marked.contains(n.label)) %7B%0A                dfs(n, nCopy, marked, copyMap);%0A       
      
-   
+%7D
 %0A   
@@ -1942,104 +1942,9 @@
     
-UndirectedGraphNode cp0 = prob.cloneGraph(n0);%0A        System.out.println(cp0.neighbors.get(0));
+%7D
 %0A   

Solve problem 133 (yay!)