Java Union-Find solution - QuickUnion


  • 0
    S

    Updated: Thanks for pointing it out @StefanPochmann

    public class Solution {
    public boolean validTree(int n, int[][] edges) {
        
        if(n <= 0)
            return false;
        
        if(edges == null || edges.length != n-1)
            return false;
        
        
        int[] unionFind = new int[n];
        
        for(int i = 0 ; i < n ; i++){
            unionFind[i] = i;
        }
        
        for(int i = 0 ; i < edges.length ; i++){
            int x = edges[i][0];
            int y = edges[i][1];
            
            if(findRoot(unionFind, x) == findRoot(unionFind, y))
                return false;
            unionFind[y] = x;
        }
        
        return true;
        
    }
    
    int findRoot(int[] unionFind, int i){
        while(i != unionFind[i])
            i = unionFind[i];
            
        return i;
    }
    

    }


  • 0

    Doesn't work, for example fails this case:

    4
    [[0,1],[2,0],[1,2]]


  • 0
    S

    Thanks! Corrected it


  • 0
    F

    Still not work on:
    5
    [[0,1],[2,1],[2,0],[2,4]].

    Guess it's because when it reads in [2,1], the code will set unionFind[1] = 2. But the root of 1 is supposed to be 0. If you set it to 2, you disconnect it with 0.

    This modification will make the code work.
    int x = Math.min(edges[i][0], edges[i][1]);
    int y = Math.max(edges[i][0], edges[i][1]);


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.