DisjointSet.cs

using System.Collections;

namespace DataStructures.DisjointSet
{
    /// <summary>
    /// Implementation of Disjoint Set with Union By Rank and Path Compression heuristics.
    /// </summary>
    /// <typeparam name="T"> generic type for implementation.</typeparam>
    public class DisjointSet<T>
    {
        /// <summary>
        /// make a new set and return its representative.
        /// </summary>
        /// <param name="x">element to add in to the DS.</param>
        /// <returns>representative of x.</returns>
        public Node<T> MakeSet(T x) => new(x);

        /// <summary>
        /// find the representative of a certain node.
        /// </summary>
        /// <param name="node">node to find representative.</param>
        /// <returns>representative of x.</returns>
        public Node<T> FindSet(Node<T> node)
        {
            if (node != node.Parent)
            {
                node.Parent = FindSet(node.Parent);
            }

            return node.Parent;
        }

        /// <summary>
        /// merge two sets.
        /// </summary>
        /// <param name="x">first set member.</param>
        /// <param name="y">second set member.</param>
        public void UnionSet(Node<T> x, Node<T> y)
        {
            Node<T> nx = FindSet(x);
            Node<T> ny = FindSet(y);
            if (nx == ny)
            {
                return;
            }

            if (nx.Rank > ny.Rank)
            {
                ny.Parent = nx;
            }
            else if (ny.Rank > nx.Rank)
            {
                nx.Parent = ny;
            }
            else
            {
                nx.Parent = ny;
                ny.Rank++;
            }
        }
    }
}