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.

Hint:

  1. Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], what should your return? Is this case a valid tree?
  2. 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:

  1. public class Solution {
  2.   public boolean validTree(int n, int[][] edges) {
  3.     int[] nums = new int[n];
  5.     Arrays.fill(nums, -1);
  7.     for (int i = 0; i < edges.length; i++) {
  8.       int x = edges[i][0];
  9.       int y = edges[i][1];
  11.       x = find(nums, x);
  12.       y = find(nums, y);
  14.       if (x == y)
  15.         return false;
  17.       nums[x] = y;
  18.     }
  20.     return edges.length == n - 1;
  21.   }
  23.   int find(int[] nums, int i) {
  24.     if (nums[i] == -1)
  25.       return i;
  27.     return find(nums, nums[i]);
  28.   }
  29. }