Given nnodes labeled from0ton - 1and a list ofundirectededges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

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.

Example

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Solution: 对每条edge两个端点进行union，若一条新的edge两点已union，说明有环，非tree

    public boolean validTree(int n, int[][] edges) {
        if(edges == null || edges.length == 0){
            if(n == 1){
                return true;
            } else{
                return false;
            }    
        }
        if (n - 1 != edges.length) {
            return false;
        }

        UnionFind uf = new UnionFind(n);
        for(int i = 0; i < edges.length; i++){
            if(edges[i].length < 2){
                continue;
            }
            if(uf.compressed_find(edges[i][0]) == uf.compressed_find(edges[i][1])){
                return false;
            } else{
                uf.union(edges[i][0], edges[i][1]);
            }
        }
        return true;
    }

    class UnionFind{
            HashMap<Integer, Integer> father = new HashMap<Integer, Integer>();

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

            public int compressed_find(int x){
                int parent = x;
                while(parent != father.get(parent)){
                    parent = father.get(parent);
                }
                int next;
                while(x != father.get(x)){
                    next = father.get(x);
                    father.put(x, parent);
                    x = next;
                }
                return parent;
            }

            public void union(int x, int y){
                int fa_x = compressed_find(x);
                int fa_y = compressed_find(y);
                if(fa_x != fa_y){
                    father.put(fa_x, fa_y);
                }
            }
    }