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.

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. 边的数目 == n(点的数目)-1
   用union and find来判断是否存在环。

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize n isolated islands
        int[] nums = new int[n];
        Arrays.fill(nums, -1);
        
        // perform union find
        for(int i=0; i<edges.length; i++){//num of edges
            int x = find(nums, edges[i][0]);
            int y = find(nums, edges[i][1]);
            
            // if two vertices happen to be in the same set
            // then there's a cycle
            if(x == y) return false;//there is a cycle
            
            //union
            nums[x] = y;
        }
        
        return edges.length == n-1;
    }
    
    private int find(int nums[], int i){
        if(nums[i] == -1) return i;//alone
        return find(nums, nums[i]);
    }
}

二刷：
首先用union and find来确认无环, 如果1->2, 那么1划到2这个集中，然后确认边的数目==点的数目-1

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] nums = new int[n];
        Arrays.fill(nums, -1);
        //union and find
        for(int[] edge : edges){
            int x = find(nums, edge[0]);
            int y = find(nums, edge[1]);
            if(x == y) return false;
            nums[x] = y;
        }
        
        return n == edges.length + 1;
    }
    
    private int find(int[] nums, int node){
        if(nums[node] == -1) return node;
        else return find(nums, nums[node]);
    }
}