Package dsa

Class QuickFindUF

java.lang.Object
dsa.QuickFindUF
All Implemented Interfaces:
UF
public class QuickFindUF extends Object implements UF
This data type provides an implementation of the Union Find (UF) API in which the find, count, and connected operations run in constant time, whereas the union operation runs in linear time.

  • Constructor Summary

    Constructors
    Constructor
    Description
    QuickFindUF(int n)
    Constructs an empty UF data structure with n sites.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    connected(int p, int q)
    Returns true if sites p and q belong to the same component, and false otherwise.
    int
    count()
    Returns the number of components.
    int
    find(int p)
    Returns the canonical site of the component containing site p.
    static void
    main(String[] args)
    Unit tests the data type.
    void
    union(int p, int q)
    Connects sites p and q.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • QuickFindUF

      public QuickFindUF(int n)
      Constructs an empty UF data structure with n sites.
      Parameters:
      n - the number of sites.

  • Method Details

    • find

      public int find(int p)
      Returns the canonical site of the component containing site p.
      Specified by:
      find in interface UF
      Parameters:
      p - a site.
      Returns:
      the canonical site of the component containing site p.

    • count

      public int count()
      Returns the number of components.
      Specified by:
      count in interface UF
      Returns:
      the number of components.

    • connected

      public boolean connected(int p, int q)
      Returns true if sites p and q belong to the same component, and false otherwise.
      Specified by:
      connected in interface UF
      Parameters:
      p - one site.
      q - the other site.
      Returns:
      true if sites p and q belong to the same component, and false otherwise.

    • union

      public void union(int p, int q)
      Connects sites p and q.
      Specified by:
      union in interface UF
      Parameters:
      p - one site.
      q - the other site.

    • main

      public static void main(String[] args)
      Unit tests the data type.
      Parameters:
      args - the command-line arguments.