Graph Valid Tree

1package pkg5leetcode.blind75;2 3/*4 * Graph Valid Tree | LC 2615 * APPROACH: n-1 edges and single connected component via Union-Find.6 * COMPLEXITY: Time O(n alpha(n)), Space O(n)7 */8public class blind75_LC261GraphValidTree {9    static boolean validTree(int n, int[][] edges) {10        if (edges.length != n - 1) return false;11        int[] parent = new int[n];12        for (int i = 0; i < n; i++) parent[i] = i;13        for (int[] e : edges) {14            int a = find(parent, e[0]), b = find(parent, e[1]);15            if (a == b) return false;16            parent[a] = b;17        }18        return true;19    }20 21    static int find(int[] p, int x) {22        while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; }23        return x;24    }25 26    public static void main(String[] args) {27        check(validTree(5, new int[][]{{0, 1}, {0, 2}, {0, 3}, {1, 4}}), "case1");28        check(!validTree(5, new int[][]{{0, 1}, {1, 2}, {2, 3}, {1, 3}, {1, 4}}), "case2");29        System.out.println("all tests passed");30    }31 32    static void check(boolean cond, String name) {33        if (!cond) throw new AssertionError("FAILED: " + name);34        System.out.println("  PASS " + name);35    }36}