Graph Valid Tree

medium graph union find

Problem

Given n nodes labeled 0..n-1 and a list of undirected edges, decide whether the resulting graph is a valid tree. A tree on n nodes has exactly n − 1 edges, is connected, and contains no cycle.

Quick test: if the number of edges is not n − 1, reject. Otherwise process edges with union-find — if union of two endpoints ever finds the same root, a cycle exists, so reject. Otherwise accept.

Inputn = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

Outputtrue

edges (a-b separated by ';')

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        parent[ra] = rb
    return True

function validTree(n, edges) {
  if (edges.length !== n - 1) return false;
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x) => { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; };
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    parent[ra] = rb;
  }
  return true;
}

class Solution {
    int[] parent;
    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) return false;
            parent[ra] = rb;
        }
        return true;
    }
    int find(int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    }
}

bool validTree(int n, vector<vector<int>>& edges) {
    if ((int)edges.size() != n - 1) return false;
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);
    function<int(int)> find = [&](int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    };
    for (auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra == rb) return false;
        parent[ra] = rb;
    }
    return true;
}

Explanation

A graph is a valid tree when it is connected and has no cycle. There's a neat shortcut: a tree on n nodes always has exactly n - 1 edges, so if the edge count is wrong we can reject right away.

The first line does exactly that: if edges.length != n - 1, return false. This single check rules out both "too few edges" (disconnected) and "too many edges" (must contain a cycle).

Once the count is right, we only need to confirm there's no cycle, and union-find is perfect for that. Each node starts as its own root in the parent array. The find function follows parent pointers up to the root (with path compression for speed).

For each edge (a, b) we compute both roots. If they are already the same, then a and b were connected before this edge, so adding it closes a loop — that's a cycle, return false. Otherwise we union the two groups by pointing one root at the other.

Example: n = 5, edges [[0,1],[0,2],[0,3],[1,4]]. There are 4 edges (= n − 1), and every union joins two separate groups with no repeated root, so it's a valid tree and the answer is true.

Time: O((n + e) · α(n)) Space: O(n)