Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and 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.

Example

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Code:

public class Solution {

    public boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) {
            return false;
        }
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < edges.length; i++) {
            int a = uf.find(edges[i][0]);
            int b = uf.find(edges[i][1]);
            if (a == b) {
                return false;
            }
            uf.union(a, b);
        }
        return true;
    }

    class UnionFind {
        private int[] father;

        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }

        public int find(int i) {
            int parent = father[i];
            while (parent != father[parent]) {
                parent = father[parent];
            }
            //update
            int temp = -1;
            int fa = father[i];
            while (fa != father[fa]) {
                temp = father[fa];
                father[fa] = parent;
                fa = temp;
            }
            return parent;
        }

        public void union(int a, int b) {
            int parentA = find(a);
            int parentB = find(b);
            father[parentB] = parentA;
        }

    }
}

results matching ""

    No results matching ""