Graph Valid Tree

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

• Time: O(N)
• Space: O(N)

class GraphValidTree {
    public boolean validTree(int n, int[][] edges) {
        UF uf = new UF(n);
        for (int i = 0; i < edges.length; i++) {
            if (!uf.union(edges[i][0], edges[i][1])) {
                return false;
            }
        }
        return uf.count == 1;
    }

    // Union Find / Quick-Find
    class UF {
        int[] roots;
        int count;

        UF(int n) {
            count = n;
            roots = new int[n];
            for (int i = 0; i < n; i++) {
                roots[i] = i;
            }
        }

        private Integer find(int p) {
            return roots[p];
        }

        public boolean union(int p, int q) {
            int pRoot = find(p);
            int qRoot = find(q);
            if (pRoot == qRoot)
                return false;
            for (int i = 0; i < roots.length; i++)
                if (roots[i] == pRoot)
                    roots[i] = qRoot;
            count--;
            return true;
        }
    }
}