Graph valid tree

Do n nodes and these undirected edges form one tree? A tree has exactly n - 1 edges and no cycle; union-find spots the cycle.

The idea

A tree is connected and has no cycle. With exactly n - 1 edges, those two properties go together: if no edge closes a cycle, every edge merges two components, and n - 1 merges take n components down to 1. So check the edge count first, then union the edges and fail on the first edge whose ends already share a root.

Code

public bool ValidTree(int n, int[][] edges) {
    if (edges.Length != n - 1) return false; // a tree on n nodes has exactly n - 1 edges
    var parent = new int[n];
    var rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    foreach (var e in edges) {
        int ra = Find(parent, e[0]), rb = Find(parent, e[1]);
        if (ra == rb) return false; // already connected: this edge makes a cycle
        if (rank[ra] < rank[rb]) (ra, rb) = (rb, ra);
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
    }
    return true; // n - 1 merges and no cycle: one connected tree
}

static int Find(int[] parent, int x) {
    if (parent[x] != x)
        parent[x] = Find(parent, parent[x]); // path compression: point x straight at its root
    return parent[x];
}

Tips

• Try n = 6 with "0 1, 1 2, 2 0, 3 4, 4 5": five edges, but 2 - 0 closes a cycle, so it is not a tree.
• Try n = 6 with "0 1, 1 2, 3 4, 4 5": only four edges, so it fails the count check before any union.
• Connectivity never needs its own check: n - 1 edges with no cycle are always connected.

In the .NET library

The edge-count guard is O(1) and rejects most invalid inputs before any array is allocated.