2ms Beat 98% Java UnionAndFind Solution


  • 0
    D
    public class Solution {
        
        int[] parent;
        
        private int findParent( int n ) {
            while ( parent[n] != n ) {
                n = parent[n];
            }
            
            return n;
        }
        
        private boolean unionFind( int p, int q ) {
            int pp = findParent(p);
            int qq = findParent(q);
            
            if ( pp == qq ) {
                return true;
            } else if ( pp < qq ) {
                parent[pp] = qq;
                return false;
            } else {
                parent[qq] = pp;
                return false;
            }
        }
        
        public int countComponents(int n, int[][] edges) {
            
            if ( n == 0 )
                return 0;
            
            parent = new int[n];
            int p, q;
            
            for ( int i = 0; i < n; i++ )
                parent[i] = i;
                
            for ( int[] pair : edges ) {
                p = pair[0];
                q = pair[1];
                if ( !unionFind( p, q ) ) {
                    n--;
                }
            }
            
            return n;
        }
    }

Log in to reply
 

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