package com.freetymekiyan.algorithms.level.medium;

/**
 * 261. Graph Valid Tree
 * <p>
 * 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. Connected acyclic graph.
     * A quick check on the # of edges lock the graph to either:
     * 1) Connected without cycle. 2) Has cycle, not all connected.
     * So if the # of edges is n-1, we only need to verify that there is no cycle.
     * Union-find can be used to build connected component and check cycle.
     * <p>
     * Implementation:
     * Quick check if # of edges is n-1.
     * Initialize an array of n distinct connected component ids.
     * For each edge in edges:
     * | Find the connected component ids for the two nodes.
     * | If the ids are the same, the two nodes are already connected, cycle found, return false.
     * | Else, union the two nodes by set x's id to y.
     * After checking all edges and finding no cycle, return true.
     */
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) { // Quick check on the number of edges. It requires n - 1 edges to connect n vertices.
            return false;
        }
        // Init CC id array.
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i;
        }
        // Check cycle.
        for (int i = 0; i < edges.length; i++) {
            // Find connected component ids of the two nodes.
            int x = find(nums, edges[i][0]);
            int y = find(nums, edges[i][1]);
            if (x == y) { // If two vertices are already connected, there is a cycle.
                return false;
            }
            // Union the 2 nodes.
            nums[x] = y; // Add edges[i][0] to one connected component.
        }
        return true;
    }

    /**
     * Recursive.
     * Find connected component id, or the root id.
     * Check whether child(current index) and parent(the value) are the same.
     * If they are, return the index.
     * If not, set index to the value and check again.
     * Stop till we find the root.
     */
    private int find(int nums[], int i) {
        while (i != nums[i]) {
            // Here if we found the child's id are not the same as the parent's.
            // We know the parent can be an intermediate id.
            // So we set parent's id to grand parent's id.
            // Which will dynamically balance the tree thus reducing O(n) to O(1).
            nums[i] = nums[nums[i]];
            i = nums[i];
        }
        return i;
    }
}
@@ -2406,19 +2406,18 @@
   int%5B%5D 
-num
+id
 s = new 
@@ -2470,27 +2470,26 @@
             
-num
+id
 s%5Bi%5D = i;%0A  
@@ -2540,37 +2540,23 @@
 (int
- i = 0; i %3C edges.length; i++
+%5B%5D edge : edges
 ) %7B%0A
@@ -2637,17 +2637,18 @@
 int 
-x
+r1
  = find(
 nums
@@ -2643,30 +2643,25 @@
  = find(
-num
+id
 s, edge
-s%5Bi%5D
 %5B0%5D);%0A  
@@ -2678,17 +2678,18 @@
 int 
-y
+r2
  = find(
 nums
@@ -2688,22 +2688,17 @@
 ind(
-num
+id
 s, edge
-s%5Bi%5D
 %5B1%5D)
@@ -2719,14 +2719,16 @@
 if (
-x
+r1
  == 
-y
+r2
 ) %7B 
@@ -2881,19 +2881,20 @@
     
-nums%5Bx
+ids%5Br1
 %5D = 
-y
+r2
 ; //
@@ -3293,19 +3293,18 @@
 ind(int 
-num
+id
 s%5B%5D, int
@@ -3329,19 +3329,18 @@
 e (i != 
-num
+id
 s%5Bi%5D) %7B%0A
@@ -3639,26 +3639,23 @@
     
-num
+id
 s%5Bi%5D = 
-nums%5Bnum
+ids%5Bid
 s%5Bi%5D
@@ -3673,19 +3673,18 @@
     i = 
-num
+id
 s%5Bi%5D;%0A  

update 261. Graph Valid Tree