Package dsa

Class QuickFindUF

  • All Implemented Interfaces:
    UF

    public class QuickFindUF
    extends Object
    implements UF
    This data type provides an implementation of the UF API in which the find operation is efficient (runs in constant time).
    • Constructor Detail

      • QuickFindUF

        public QuickFindUF​(int n)
        Constructs an empty union-find data structure with n sites.
        Parameters:
        n - the number of sites.
    • Method Detail

      • find

        public int find​(int p)
        Description copied from interface: UF
        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()
        Description copied from interface: UF
        Returns the number of components.
        Specified by:
        count in interface UF
        Returns:
        the number of components.
      • connected

        public boolean connected​(int p,
                                 int q)
        Description copied from interface: UF
        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)
        Description copied from interface: UF
        Connects sites p and q if they are not already connected.
        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.