Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Quick-Find Algorithm
public class QuickFindUF
{
private int[] id; // id[i] = component identifier of i
private int count; // number of components
public QuickFindUF( int n )
{
count = n;
id = new int[ n ];
for ( int i = 0; i < n; i++ )
id[ i ] = i;
}
public int count() { return count; }
public int find( int p )
{
validate( p );
return id[ p ];
}
private void validate( int p )
{
int n = id.length;
if ( p < 0 || p >= n )
{
throw new IllegalArgumentException( "index " + p + " is not between 0 and " + ( n - 1 ) );
}
}
public boolean connected( int p, int q )
{
validate( p );
validate( q );
return id[ p ] == id[ q ];
}
public void union( int p, int q )
{
validate( p );
validate( q );
int pID = id[ p ]; // needed for correctness
int qID = id[ q ]; // to reduce the number of array accesses
if ( pID == qID ) return;
for ( int i = 0; i < id.length; i++ )
if ( id[ i ] == pID ) id[ i ] = qID;
count--;
}
public static void main( String[] args )
{
int n = StdIn.readInt();
QuickFindUF uf = new QuickFindUF( n );
while ( !StdIn.isEmpty() )
{
int p = StdIn.readInt();
int q = StdIn.readInt();
if ( uf.connected( p, q ) ) continue;
uf.union( p, q );
StdOut.println( p + " " + q );
}
StdOut.println( uf.count() + " components" );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment