Disjoint Set(Union Set)

DisjointSet.java

import java.util.*;

// a DisjointSet instance stands for a disjoint set that knows all its nodes
public class DisjointSet<T> {

    // the nodes in each DisjointSet instance
    public static class Node<T> {
        // the value of each node
        public final T val;
        // the parent of each node, defaut itself
        private Node<T> pa = this;

        public Node(T val) {
            this.val = val;
        }

        public Node<T> getParent() {
            return pa;
        }

        private void setParent(Node<T> pa) {
            this.pa = pa;
        }
    }

    // record all the nodes in this disjoint set
    private final Set<Node<T>> setRecord;

    public DisjointSet() {
        this.setRecord = new HashSet<>();
    }

    // make a set using value
    public Node<T> makeSet(T u) {
        Node<T> newNode = new Node<>(u);
        setRecord.add(newNode);
        return newNode;
    }

    private Node<T> findHelper(Node<T> u) {
        if (u.getParent() != u) {
            u.setParent(findHelper(u.getParent()));
        }
        return u.getParent();
    }

    // finding helper
    public Node<T> find(Node<T> u) {
        if (setRecord.contains(u)) {
            return findHelper(u);
        } else {
            return null;
        }
    }

    // merge u to v
    public void union(Node<T> u, Node<T> v) {
        Node<T> uPa = find(u);
        Node<T> vPa = find(v);
        if (uPa != vPa) {
            uPa.setParent(vPa);
        }
    }
}