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

并查集做，若给的edges中一组数在一个集合里，表示有环了，返回false，否则将这组数连起来。最后只剩一个集合为true
class Solution {
    class UnionFind{
        Map<Integer, Integer> father = new HashMap<>();

        public UnionFind(int n) {
            for(int i = 0; i < n; i++) {
                father.put(i, i);
            }
        }

        public int find(int x) {
            List<Integer> path = new ArrayList<>();
            while(father.get(x) != x) {
                path.add(x);
                x = father.get(x);
            }

            for(Integer i : path) {
                father.put(i, x);
            }

            return x;
        }

        public void union(int a, int b) {
            int ar = find(a);
            int br = find(b);
            if(ar != br) {
                father.put(ar, br);
            }
        }
    }

    public boolean validTree(int n, int[][] edges) {
        if(n == 1) return true;
        if(n > 1 && (edges == null || edges.length == 0 || edges[0].length == 0)) return false;
        UnionFind uf = new UnionFind(n);
        int count = n;
        for(int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            int aFa = uf.find(a);
            int bFa = uf.find(b);
            if(aFa == bFa) return false;
            uf.union(a, b);
            count--;
        }
        if(count == 1) return true;
        return false;
    }
}

改进版。之前就判断n - 1 != edges.length的话肯定就false，这样后面只要判断edges中给出的一组数是不是在一个集合里。
class Solution {
    class UnionFind{
        Map<Integer, Integer> father = new HashMap<>();

        public UnionFind(int n) {
            for(int i = 0; i < n; i++) {
                father.put(i, i);
            }
        }

        public int find(int x) {
            List<Integer> path = new ArrayList<>();
            while(father.get(x) != x) {
                path.add(x);
                x = father.get(x);
            }

            for(Integer i : path) {
                father.put(i, x);
            }

            return x;
        }

        public void union(int a, int b) {
            int ar = find(a);
            int br = find(b);
            if(ar != br) {
                father.put(ar, br);
            }
        }
    }

    public boolean validTree(int n, int[][] edges) {
        if(n - 1 != edges.length) return false;

        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < edges.length; i++) {
            int a = edges[i][0];
            int b = edges[i][1];
            int aFa = uf.find(a);
            int bFa = uf.find(b);
            if(aFa == bFa) return false;
            uf.union(a, b);
        }
        return true;
    }
}