@@ -0,0 +1,2435 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * 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%0A * to check whether these edges make up a valid tree.%0A * %3Cp%3E%0A * For example:%0A * %3Cp%3E%0A * Given n = 5 and edges = %5B%5B0, 1%5D, %5B0, 2%5D, %5B0, 3%5D, %5B1, 4%5D%5D, return true.%0A * %3Cp%3E%0A * Given n = 5 and edges = %5B%5B0, 1%5D, %5B1, 2%5D, %5B2, 3%5D, %5B1, 3%5D, %5B1, 4%5D%5D, return false.%0A * %3Cp%3E%0A * Hint:%0A * %3Cp%3E%0A * Given n = 5 and edges = %5B%5B0, 1%5D, %5B1, 2%5D, %5B3, 4%5D%5D, what should your return? Is this case a valid tree?%0A * According to the definition of tree on Wikipedia: %E2%80%9Ca tree is an undirected graph in which any two vertices are%0A * connected by exactly one path. In other words, any connected graph without simple cycles is a tree.%E2%80%9D%0A * Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, %5B0, 1%5D is the same%0A * as %5B1, 0%5D and thus will not appear together in edges.%0A * %3Cp%3E%0A * Company Tags: Google, Facebook, Zenefits%0A * Tags: Depth-first Search, Breadth-first Search, Graph, Union Find%0A * Similar Problems: (M) Course Schedule, (M) Number of Connected Components in an Undirected Graph%0A */%0Apublic class GraphValidTree %7B%0A%0A    /**%0A     * Union Find.%0A     * What is the difference between tree and graph?%0A     * Tree is a special graph: 1) All connected. 2) No cycle.%0A     * Union-find can be used to build connected component and check connection.%0A     */%0A    public boolean validTree(int n, int%5B%5D%5B%5D edges) %7B%0A        int%5B%5D nums = new int%5Bn%5D;%0A        for (int i = 0; i %3C n; i++) %7B%0A            nums%5Bi%5D = i;%0A        %7D%0A%0A        for (int i = 0; i %3C edges.length; i++) %7B%0A            int x = find(nums, edges%5Bi%5D%5B0%5D); // Find connected component id for one vertex%0A            int y = find(nums, edges%5Bi%5D%5B1%5D); // Find connected component id for the other%0A            // Two vertices are already connected%0A            if (x == y) %7B%0A                return false;%0A            %7D%0A            // Union%0A            nums%5Bx%5D = y; // Add edges%5Bi%5D%5B0%5D to the connected component%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            // Dynamically balance the tree while finding%0A            nums%5Bi%5D = nums%5Bnums%5Bi%5D%5D;%0A            i = nums%5Bi%5D;%0A        %7D%0A        return i;%0A    %7D%0A%0A%7D%0A

add graph valid tree