Java 12ms union find


  • 0
    B

    The part of building indirect relationship is tricky. might go back to this if i find a simpler way.

    EDIT: indirect relationship made simple.

        public int findCircleNum(int[][] M) {
            
            if (M.length == 0)
                return 0;
    
            if (M.length == 1)
                return 1;
            
            int[] root = new int[M.length];
            
            for (int i = 0; i < M.length; i++)
                root[i] = i;
            
            for (int i = 0; i < M.length; i++)
                for (int j = i + 1; j < M[0].length; j++) //only scan half of matrix, ignore the x.x
                   
                    if (M[i][j] == 1){
                        
                        int x = i;
                        while(x != root[x])
                            x = root[root[x]]; 
    
                        int y = j;
                        while(y != root[y])
                            y = root[root[y]]; 
    
                        if (x < y)
                            root[y] = x;
                        else
                            root[x] = y;
    
                    }
    
            int count = 0;
    
            for (int i = 0; i < M.length; i++){
                if (i == root[i])
                    count++;
            }
            return count;
        }
    

Log in to reply
 

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