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.

For example:

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.

No cycle, Connected undirected graph.


Union found

    public boolean validTree(int n, int[][] edges) {
        if(n <= 1) return true;

        int [] union = new int[n];
        int unionNumber = n;

        Arrays.fill(union, -1);

        for(int []edge : edges){

            if(edge[0] > edge[1]) swap(edge, 0, 1);
            int e1 = edge[0], e2 = edge[1];

            while(union[e1] != -1)
                e1 = union[e1];
            while(union[e2] != -1)
                e2 = union[e2];

            if(e1 == e2) return false;

            union[e2] = e1;
            unionNumber --;
        }

        return unionNumber == 1;
    }

    private void swap(int []nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

results matching ""

    No results matching ""