Last active
September 16, 2019 15:56
-
-
Save lawrencechen0921/826732e2cbac8fa26001f82beae39b61 to your computer and use it in GitHub Desktop.
Quick Find
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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