package com.fishercoder.solutions;

/**
 *261. Graph Valid Tree
 *Given n nodes labeled from 0 to n - 1 and a list of undirected edges
 * (each edge is a pair of nodes),
 * write a function to check whether these edges make up a valid tree.

 For example:

 Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

 Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

 Hint:

 Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
 According to the definition of tree on Wikipedia:
 “a tree is an undirected graph in which any two vertices are connected by exactly one path.
 In other words, any connected graph without simple cycles is a tree.”

 Note: you can assume that no duplicate edges will appear in edges.
 Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
 */
public class _261 {

    public boolean validTree(int n, int[][] edges) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i;
        }

        for (int i = 0; i < edges.length; i++) {
            int x = find(nums, edges[i][0]);
            int y = find(nums, edges[i][1]);

            if (x == y) {
                return false;
            }

            //union
            nums[x] = y;
        }

        return edges.length == n - 1;
    }

    int find(int[] nums, int i) {
        if (nums[i] == i) {
            return i;
        }
        return find(nums, nums[i]);
    }
}

@@ -59,16 +59,20 @@
  Tree%0A *
+%0A * 
 Given n 
@@ -935,16 +935,56 @@
 _261 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -1036,16 +1036,20 @@
         
+ 
+   
 int%5B%5D nu
@@ -1065,16 +1065,20 @@
 int%5Bn%5D;%0A
+    
         
@@ -1115,24 +1115,28 @@
             
+ 
+   
 nums%5Bi%5D = i;
@@ -1136,32 +1136,36 @@
 i%5D = i;%0A        
+    
 %7D%0A%0A        for (
@@ -1151,32 +1151,36 @@
      %7D%0A%0A        
+ 
+   
 for (int i = 0; 
@@ -1212,24 +1212,28 @@
             
+    
 int x = find
@@ -1261,24 +1261,28 @@
             
+ 
+   
 int y = find
@@ -1311,24 +1311,28 @@
             
+    
 if (x == y) 
@@ -1341,32 +1341,36 @@
                 
+  
+  
 return false;%0A  
@@ -1371,32 +1371,36 @@
 se;%0A            
+    
 %7D%0A%0A            /
@@ -1402,16 +1402,20 @@
     
+  
+  
 //union%0A
     
@@ -1410,16 +1410,20 @@
 //union%0A
+    
         
@@ -1439,35 +1439,43 @@
 x%5D = y;%0A        
+  
+  
 %7D%0A%0A
+    
         return e
@@ -1496,27 +1496,35 @@
  n - 1;%0A    
+  
+  
 %7D%0A%0A
+    
     int find
@@ -1549,24 +1549,28 @@
 ) %7B%0A        
+  
+  
 if (nums%5Bi%5D 
@@ -1585,24 +1585,28 @@
             
+    
 return i;%0A  
@@ -1611,18 +1611,26 @@
         
+  
-%7D%0A
+  %7D%0A    
         
@@ -1653,20 +1653,30 @@
 , nums%5Bi%5D);%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 261