Disjoint Set

DisjointSet.php

<?php
declare(strict_types=1);

class DisjointSet
{
    private $parent = [];
    private $rank = [];

    public function makeSet(int $i): void
    {
        $this->parent[$i] = $i;
        $this->rank[$i] = 0;
    }

    public function find(int $i): ?int
    {
        if (! isset($this->parent[$i])) {
            return null;
        }

        if ($i !== $this->parent[$i]) {
            $this->parent[$i] = $this->find($this->parent[$i]);
        }

        return $this->parent[$i];
    }

    public function union(int $i, int $j): void
    {
        $rootI = $this->find($i);
        $rootJ = $this->find($j);

        if ($rootI === null || $rootJ === null) {
            throw new \Exception('Unknown set.');
        }

        if ($rootI === $rootJ) {
            return;
        }

        if ($this->rank[$rootI] > $this->rank[$rootJ]) {
            $this->parent[$rootJ] = $rootI;
        } else {
            $this->parent[$rootI] = $rootJ;
            if ($this->rank[$rootI] === $this->rank[$rootJ]) {
                $this->rank[$rootJ]++;
            }
        }
    }
}