Union-Find (Disjoint Set) – PHP implementation, cycle detection, deduplication

Union-Find (Disjoint Set Union) is a data structure for managing disjoint sets. It supports two operations in nearly O(1) time: checking whether two elements belong to the same set (Find) and merging two sets (Union). The algorithm appears in graph problems, cycle detection and element grouping. In Magento 2 it is useful for merging duplicate customers and products.

Idea – a forest of trees

Each element points to its parent. The root of a tree points to itself. Elements in the same tree belong to the same set. Find follows pointers to the root. Union merges two trees by attaching one root under the other.

Sets: {1,4,7} {2,5} {3,6,8}

parent: [_, 1, 2, 3, 1, 2, 3, 1, 3]
         0  1  2  3  4  5  6  7  8

Find(7): 7->1->1 (root) = 1
Find(4): 4->1->1 (root) = 1
Find(7) == Find(4) => same set ✓

Union(1,2): attach root 2 under root 1
parent[2] = 1
Now: {1,2,4,5,7} {3,6,8}

PHP implementation

<?php

declare(strict_types=1);

class UnionFind
{
    private array $parent;
    private array $rank;
    private int   $count;

    public function __construct(int $n)
    {
        $this->count  = $n;
        $this->parent = range(0, $n - 1);
        $this->rank   = array_fill(0, $n, 0);
    }

    // Find with path compression - O(α(n)) amortised, practically O(1)
    public function find(int $x): int
    {
        if ($this->parent[$x] !== $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    // Union by rank
    public function union(int $x, int $y): bool
    {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX === $rootY) return false;

        if ($this->rank[$rootX] < $this->rank[$rootY]) {
            $this->parent[$rootX] = $rootY;
        } elseif ($this->rank[$rootX] > $this->rank[$rootY]) {
            $this->parent[$rootY] = $rootX;
        } else {
            $this->parent[$rootY] = $rootX;
            $this->rank[$rootX]++;
        }

        $this->count--;
        return true;
    }

    public function connected(int $x, int $y): bool { return $this->find($x) === $this->find($y); }
    public function getCount(): int                  { return $this->count; }
}

Application 1 – cycle detection in a graph

<?php

function hasCycle(int $vertices, array $edges): bool
{
    $uf = new UnionFind($vertices);

    foreach ($edges as [$u, $v]) {
        if ($uf->connected($u, $v)) {
            return true; // edge connects already-connected vertices = cycle
        }
        $uf->union($u, $v);
    }

    return false;
}

$moduleGraph = [
    [0, 1], // ModuleA depends on ModuleB
    [1, 2], // ModuleB depends on ModuleC
    [2, 3], // ModuleC depends on ModuleD
    // [3, 0] // ModuleD depends on ModuleA - this would be a cycle!
];

echo hasCycle(4, $moduleGraph) ? "Cycle detected!" : "Acyclic graph";

Application 2 – grouping duplicate customers

<?php

declare(strict_types=1);

class CustomerDeduplicator
{
    public function findDuplicateGroups(array $customers): array
    {
        $n  = count($customers);
        $uf = new UnionFind($n);

        $emailIndex = [];
        $phoneIndex = [];

        foreach ($customers as $i => $customer) {
            $email = strtolower($customer['email']);
            $phone = preg_replace('/[^0-9]/', '', $customer['phone'] ?? '');

            if (isset($emailIndex[$email])) {
                $uf->union($i, $emailIndex[$email]);
            }
            $emailIndex[$email] = $i;

            if ($phone && isset($phoneIndex[$phone])) {
                $uf->union($i, $phoneIndex[$phone]);
            }
            if ($phone) $phoneIndex[$phone] = $i;
        }

        $groups = [];
        foreach ($customers as $i => $customer) {
            $root = $uf->find($i);
            $groups[$root][] = $customer;
        }

        return array_filter($groups, fn($g) => count($g) > 1);
    }
}

$customers = [
    ['id' => 1, 'email' => 'jan@example.com',  'phone' => '600100200', 'name' => 'Jan K.'],
    ['id' => 2, 'email' => 'jan@example.com',  'phone' => '700200300', 'name' => 'Jan Kowalski'],
    ['id' => 3, 'email' => 'anna@example.com', 'phone' => '600100200', 'name' => 'Anna K.'],
    ['id' => 4, 'email' => 'piotr@example.com','phone' => '500400300', 'name' => 'Piotr N.'],
];

// Result: customers 1, 2, 3 are in one group
// (1 and 2 share email, 1 and 3 share phone)
// Customer 4 is separate

Complexity

α(n) is the inverse Ackermann function – it grows so slowly that for all practical values of n it is at most 4.

Summary

Union-Find is a simple-to-implement structure with near-linear complexity for dynamic set management. Key optimisations: path compression in Find and union by rank eliminate linear paths. Classic applications: cycle detection in graphs, Kruskal’s algorithm (MST), connected graph components and data deduplication.