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 static class Solution1 {
        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]);
        }
    }
}

@@ -33,893 +33,8 @@
 s;%0A%0A
-/**%0A *261. Graph Valid Tree%0A *%0A * Given n nodes labeled from 0 to n - 1 and a list of undirected edges%0A * (each edge is a pair of nodes),%0A * write a function to check whether these edges make up a valid tree.%0A%0A For example:%0A%0A Given n = 5 and edges = %5B%5B0, 1%5D, %5B0, 2%5D, %5B0, 3%5D, %5B1, 4%5D%5D, return true.%0A%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%0A Hint:%0A%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:%0A %E2%80%9Ca tree is an undirected graph in which any two vertices are connected by exactly one path.%0A In other words, any connected graph without simple cycles is a tree.%E2%80%9D%0A%0A Note: you can assume that no duplicate edges will appear in edges.%0A Since all edges are undirected, %5B0, 1%5D is the same as %5B1, 0%5D and thus will not appear together in edges.%0A */%0A
 publ

refactor 261