Package edu.princeton.cs.algs4

Class UF

  • public class UF
extends Object
    The UF class represents a union–find data type (also known as the disjoint-sets data type). It supports the classic union and find operations, along with a count operation that returns the total number of sets.

    The union–find data type models a collection of sets containing n elements, with each element in exactly one set. The elements are named 0 through n–1. Initially, there are n sets, with each element in its own set. The canonical element of a set (also known as the root, identifier, leader, or set representative) is one distinguished element in the set. Here is a summary of the operations:

    • find(p) returns the canonical element of the set containing p. The find operation returns the same value for two elements if and only if they are in the same set.
    • union(p, q) merges the set containing element p with the set containing element q. That is, if p and q are in different sets, replace these two sets with a new set that is the union of the two.
    • count() returns the number of sets.

    The canonical element of a set can change only when the set itself changes during a call to union—it cannot change during a call to either find or count.

    This implementation uses weighted quick union by rank with path compression by halving. The constructor takes Θ(n) time, where n is the number of elements. The union and find operations take Θ(log n) time in the worst case. The count operation takes Θ(1) time. Moreover, starting from an empty data structure with n sites, any intermixed sequence of m union and find operations takes O(m α(n)) time, where α(n) is the inverse of Ackermann's function.

    For alternative implementations of the same API, see QuickUnionUF, QuickFindUF, and WeightedQuickUnionUF. For additional documentation, see Section 1.5 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

      Constructors 
      Constructor Description
      UF​(int n)
      Initializes an empty union-find data structure with n elements 0 through n-1.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int count()
      Returns the number of sets.
      int find​(int p)
      Returns the canonical element of the set containing element p.
      static void main​(String[] args)
      Reads an integer n and a sequence of pairs of integers (between 0 and n-1) from standard input, where each integer in the pair represents some element; if the elements are in different sets, merge the two sets and print the pair to standard output.
      void union​(int p, int q)
      Merges the set containing element p with the set containing element q.

    • Constructor Detail

      • UF

        public UF​(int n)
        Initializes an empty union-find data structure with n elements 0 through n-1. Initially, each element is in its own set.
        Parameters:
        n - the number of elements
        Throws:
        IllegalArgumentException - if n < 0

    • Method Detail

      • find

        public int find​(int p)
        Returns the canonical element of the set containing element p.
        Parameters:
        p - an element
        Returns:
        the canonical element of the set containing p
        Throws:
        IllegalArgumentException - unless 0 <= p < n

      • count

        public int count()
        Returns the number of sets.
        Returns:
        the number of sets (between 1 and n)

      • union

        public void union​(int p,
                  int q)
        Merges the set containing element p with the set containing element q.
        Parameters:
        p - one element
        q - the other element
        Throws:
        IllegalArgumentException - unless both 0 <= p < n and 0 <= q < n

      • main

        public static void main​(String[] args)
        Reads an integer n and a sequence of pairs of integers (between 0 and n-1) from standard input, where each integer in the pair represents some element; if the elements are in different sets, merge the two sets and print the pair to standard output.
        Parameters:
        args - the command-line arguments