Union-find algorithm

A union-find algorithm is an algorithm that allows for manipulating and exploring a “union find” (AKA “disjoint-set”) data structure
A Java interface for this “union find” data type might look like this:

public class UF
  UF(int N)                         // initialize dynamic connectivity structure with N objects
  void union(int p, int q)          // add edge between p and q
  boolean connected(int p, int q)   // check if p and q are within the same component

Dynamic connectivity client:
- Initialize graph with N vertices
- Loop:
  - for a given unconnected pair of integers, connect them

Code:

public static void main(String[] args)
{
  int N = StdIn.readInt();
  UF uf = new UF(N);
  
  while (!StdIn.isEmpty())
  {
    int p = StdIn.readInt();
    int q = StdIn.readInt();
    
    if (!uf.connected(p, q))
    {
      uf.union(p, q);
      StdOut.println(p + " " + q);
    }
  }
}

Input:

Implementation approaches include:
applications