261. Graph Valid Tree

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.

Example 1:

Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]]
Output: true

Example 2:

Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]]
Output: false

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.

--------------------
树的条件：
1. 没环
2. 所有的node都是连接在一起

class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] nums = new int[n];
        int[] sizes = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i;
            sizes[i] = 1;
        }
        
        for (int[] e : edges) {
            int root1 = find(nums, e[0]);
            int root2 = find(nums, e[1]);
            if (root1 == root2) return false;
            
            if (sizes[root1] > sizes[root2]) {
                nums[root2] = root1;    
            }else {
                nums[root1] = root2;    
            }
        }
        
        int root = find(nums,0);
        for (int i = 1; i < n; i++) {
            if (root != find(nums, i)) return false;
        }
        
        return true;
    }
    
    private int find(int[] nums, int i) {
        while (i != nums[i]) {
            i = nums[i];
        }
        
        return i;
    }
    
    
}