Graph Valid Tree

Examples:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Output: true

Explanation: The given edges form a valid tree because they connect all nodes and do not contain any cycles.

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

Output: false

Explanation: The given edges do not form a valid tree because they contain a cycle (1-2-3-1).

Solutions

Union-Find

Time: O(n + m)Space: O(n)

The Union-Find approach is used to solve this problem. We initialize the parent array with each node as its own parent and the rank array with all zeros. We then iterate over the edges and check if the two nodes of each edge are in the same set. If they are, we return false because a cycle is detected. Otherwise, we union the two sets. Finally, we check if all nodes are in the same set by finding the parent of each node and adding it to a set. If the size of the set is 1, it means all nodes are in the same set and we return true. Otherwise, we return false.


public boolean validTree(int n, int[][] edges) {
  int[] parent = new int[n];
  int[] rank = new int[n];
  for (int i = 0;
  i < n;
  i++) {
    parent[i] = i;
  }
  for (int[] edge : edges) {
    int x = edge[0];
    int y = edge[1];
    if (find(parent, x) == find(parent, y)) {
      return false;
    }
    union(parent, rank, x, y);
  }
  Set<Integer> set = new HashSet<>();
  for (int i = 0;
  i < n;
  i++) {
    set.add(find(parent, i));
  }
  return set.size() == 1;
}

private int find(int[] parent, int x) {
  if (parent[x] != x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}

private void union(int[] parent, int[] rank, int x, int y) {
  int rootX = find(parent, x);
  int rootY = find(parent, y);
  if (rootX != rootY) {
    if (rank[rootX] > rank[rootY]) {
      parent[rootY] = rootX;
    }
    else if (rank[rootX] < rank[rootY]) {
      parent[rootX] = rootY;
    }
    else {
      parent[rootY] = rootX;
      rank[rootX]++;
    }
  }

Constraints:

Examples:

Solutions

Union-Find

Follow-up: