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.

function validTree(n, edges) {
  let parent = Array(n)
    .fill(0)
    .map((_, i) => i);
  let rank = Array(n).fill(0);

  function find(x) {
    if (parent[x] !== x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  function union(x, y) {
    let rootX = find(x);
    let rootY = find(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]++;
      }
    }
  }
  for (let [x, y] of edges) {
    if (find(x) === find(y)) {
      return false;
    }
    union(x, y);
  }
  let set = new Set();
  for (let i = 0; i < n; i++) {
    set.add(find(i));
  }
  return set.size === 1;
}

Constraints:

Examples:

Solutions

Union-Find

Follow-up: