Quick Find

Quick Find Algoritm.java

public class QuickFindUF
{
     private int [ ] id;
  
     public QuickFindUF( int N)
     {
          id = new int[N];                                                       # set id of each object to itself { N array accesses}
          for  ( int  i = 0 ;  i  <  N ;  i ++)
                id[ i ] = i ;
     }
  
      public boolean connected( int  p  ,  int  q)             #check whether p and q are in the same component { 2 array accesses}
      {   return id [ p] == id[ q] ;        }
   
      public void union (int p , int q)
      {
               int pid = id [p] ;
               int qid = id [q] ;
               for ( int i =1 ;  i < id . lengh ;  i ++ )                            #change all entries witih id[ p ] to id [ q ] { at most 2N + 2 array accesses)
                     if ( id[ i ] ==  pid )  id [ i ]  =  qid ;
      }
}