Quick-Find Algorithm

QuickFindUF.java

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" );
    }
}