Givennnodes labeled from0ton-1and 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 inedges. Since all edges are undirected,[0,1]is the same as[1,0]and thus will not appear together inedges.

class Solution {
    private class UnionFind{
        int[] father;

        public UnionFind(int n){
            father = new int[n];
            for (int i = 0; i < n; i++){
                father[i] = i;
            }
        }

        public int find(int x){
            if (father[x] == x) return x;

            return father[x] = find(father[x]);
        }

        public void union(int a, int b){
            int father_a = find(a);
            int father_b = find(b);

            if (father_a != father_b){
                father[father_a] = father_b;
            }
        }
    }

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

        UnionFind uf = new UnionFind(n);

        for (int[] edge : edges){
            if (uf.find(edge[0]) == uf.find(edge[1])) return false;

            uf.union(edge[0], edge[1]);
        }

        return true;
    }
}