package com.freetymekiyan.algorithms.level.medium;

/**
 * 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.
 * <p>
 * For example:
 * <p>
 * Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
 * <p>
 * Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.
 * <p>
 * Hint:
 * <p>
 * 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.
 * <p>
 * Company Tags: Google, Facebook, Zenefits
 * Tags: Depth-first Search, Breadth-first Search, Graph, Union Find
 * Similar Problems: (M) Course Schedule, (M) Number of Connected Components in an Undirected Graph
 */
public class GraphValidTree {

    /**
     * Union Find.
     * What is the difference between tree and graph?
     * Tree is a special graph: 1) All connected. 2) No cycle.
     * Union-find can be used to build connected component and check connection.
     */
    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]); // Find connected component id for one vertex
            int y = find(nums, edges[i][1]); // Find connected component id for the other
            // Two vertices are already connected
            if (x == y) {
                return false;
            }
            // Union
            nums[x] = y; // Add edges[i][0] to the connected component
        }

        // It requires n - 1 edges to connect n vertices.
        return edges.length == n - 1;
    }

    /**
     * Find connected component id.
     */
    private int find(int nums[], int i) {
        while (i != nums[i]) {
            // Dynamically balance the tree while finding
            nums[i] = nums[nums[i]];
            i = nums[i];
        }
        return i;
    }

}

@@ -1340,16 +1340,41 @@
 o cycle.
+ Connected acyclic graph.
 %0A     * 
@@ -1457,62 +1457,731 @@
    *
-/%0A    public boolean validTree(int n, int%5B%5D%5B%5D edges) %7B
+ %3Cp%3E%0A     * Implementation:%0A     * Quick check: It requires n-1 edges to connect n vertices. So if edges.length != n-1, return false.%0A     * Initialize an array of connected component ids.%0A     * For each edge in edges:%0A     * %7C Find the connected component ids for the two nodes.%0A     * %7C If the ids are the same, the two nodes are already connected, return false.%0A     * %7C Else, union the two nodes by set x's id to y.%0A     * After checking all edges, return true.%0A     */%0A    public boolean validTree(int n, int%5B%5D%5B%5D edges) %7B%0A        // Quick check on the number of edges. It requires n - 1 edges to connect n vertices.%0A        if (edges.length != n - 1) %7B%0A            return false;%0A        %7D%0A        // Init cc id array.
 %0A   
@@ -2275,32 +2275,55 @@
  = i;%0A        %7D%0A
+        // Check cycle.
 %0A        for (in
@@ -2371,41 +2371,8 @@
     
- int x = find(nums, edges%5Bi%5D%5B0%5D);
  // 
@@ -2402,23 +2402,27 @@
 t id
- for one vertex
+s of the two nodes.
 %0A   
@@ -2434,17 +2434,17 @@
     int 
-y
+x
  = find(
@@ -2462,74 +2462,91 @@
 %5Bi%5D%5B
-1%5D); // Find connected component id for the other%0A            // T
+0%5D);%0A            int y = find(nums, edges%5Bi%5D%5B1%5D);%0A            if (x == y) %7B // If t
 wo v
@@ -2578,34 +2578,9 @@
 cted
-%0A            if (x == y) %7B
+.
 %0A   
@@ -2711,16 +2711,17 @@
 omponent
+.
 %0A       
@@ -2727,253 +2727,629 @@
   %7D%0A
+        return true;
 %0A    
+%7D%0A%0A
     /
-/ It requires n - 1 edges to connect n vertices.%0A        return edges.length == n - 1;%0A    %7D%0A%0A    /**%0A     * Find connected component id.%0A     */%0A    private int find(int nums%5B%5D, int i) %7B%0A        while (i != nums%5Bi%5D) %7B%0A            // D
+**%0A     * Recursive.%0A     * Find connected component id, or the root id.%0A     * Check whether child(current index) and parent(the value) are the same.%0A     * If they are, return the index.%0A     * If not, set index to the value and check again.%0A     * Stop till we find the root.%0A     */%0A    private int find(int nums%5B%5D, int i) %7B%0A        while (i != nums%5Bi%5D) %7B%0A            // Here if we found the child's id are not the same as the parent's.%0A            // We know the parent can be an intermediate id.%0A            // So we set parent's id to grand parent's id.%0A            // Which will d
 ynam
@@ -3376,21 +3376,35 @@
 ree 
-while finding
+thus reducing O(n) to O(1).
 %0A   

update graph valid tree