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.

Hint:

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
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.

Solution

public class Solution {


    public boolean validTree(int n, int[][] edges) {
        int parent[] = new int[n];
        for(int i = 0; i < n; i++) parent[i] = i;

        for(int i = 0; i < edges.length; i++) {
            int ancestor0 = find(edges[i][0], parent);
            int ancestor1 = find(edges[i][1], parent);
            if(ancestor0 == ancestor1) return false;
            parent[ancestor0] = ancestor1;
        }

        for(int i = 1; i < n; i++) {
            if(find(i, parent) != find(i-1, parent)) return false;
        }
        return true;
    }

    public int find(int node, int[] parent) {
        if(parent[node] == node) return node;

        int ancestor = find(parent[node], parent);
        parent[node] = ancestor;
        return ancestor;
    }
}