Skip to content

Instantly share code, notes, and snippets.

@lawrencechen0921
Last active September 16, 2019 15:56
Show Gist options
  • Save lawrencechen0921/826732e2cbac8fa26001f82beae39b61 to your computer and use it in GitHub Desktop.
Save lawrencechen0921/826732e2cbac8fa26001f82beae39b61 to your computer and use it in GitHub Desktop.
Quick Find
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 ;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment