How to create a disjoint-set data structure, in Java?

A disjoint-set data structure, also known as a union-find data structure, is a data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It supports two main operations:

1. find(x): returns the representative element (also known as the root) of the subset that contains element x.
2. union(x, y): combines the subsets that contain elements x and y into a single subset.

Here is an example of how you can implement a disjoint-set data structure in Java:

import java.util.HashMap;
import java.util.Map;

class DisjointSet {
  private Map<Integer, Node> map = new HashMap<>();

  // Inner class to represent a node in the disjoint-set
  class Node {
    int data;
    Node parent;
    int rank;
  }

  // Makes a set with only one element and returns its representative
  public int makeSet(int data) {
    Node node = new Node();
    node.data = data;
    node.parent = node;
    node.rank = 0;
    map.put(data, node);
    return node.data;
  }

  // Finds the representative of the set that x belongs to
  public int findSet(int data) {
    return findSet(map.get(data)).data;
  }

  // Finds the representative recursively and does path
  // compression as well
  private Node findSet(Node node) {
    Node parent = node.parent;
    if (parent == node) {
      return parent;
    }
    node.parent = findSet(node.parent);
    return node.parent;
  }

  // Unites the set that includes x and the set that includes y
  // Based on rank
  public void union(int data1, int data2) {
    Node node1 = map.get(data1);
    Node node2 = map.get(data2);

    Node parent1 = findSet(node1);
    Node parent2 = findSet(node2);

    // If they are part of the same set, do nothing
    if (parent1.data == parent2.data) {
      return;
    }

    // Else, whoever has a higher rank becomes the parent
    if (parent1.rank >= parent2.rank) {
      // Increment rank only if both sets have the same rank
      parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1