Union Find

Graph Valid Tree

Givennnodes labeled from0ton - 1and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], returntrue.

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], returnfalse.

Note: you can assume that no duplicate edges will appear inedges. Since all edges are undirected,[0, 1]is the same as[1, 0]and thus will not appear together inedges.

union find

https://www.geeksforgeeks.org/union-find/

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n == 1 && edges.length == 0) {
            return true;
        }
        if (n < 1 ||edges == null || edges.length + 1 != n) {
            return false;
        }
        //find and union
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = -1;
        }
        for (int[] edge : edges) {
            int x = find(parent, edge[0]);
            int y = find(parent, edge[1]);
            if (x == y) return false;
            parent[x] = y;
        }
        return true;
    }
    public int find (int[] parent, int num) {
        while(parent[num] != -1) {
            num = parent[num];
        }
        return num;
    }

}