union-find.ts

function getGroups(
  allSuppliers: { id: string; score: number }[],
  results: { left: string; right: string }[]
) {
  const groups: Record<string, string> = {};
  for (const { id } of allSuppliers) {
    groups[id] = id;
  }
  const scoreMap: Record<string, number> = {};
  for (const { id, score } of allSuppliers) {
    scoreMap[id] = score;
  }
  for (const { left, right } of results) {
    const leftRoot = findRoot(groups, left);
    const rightRoot = findRoot(groups, right);
    if (leftRoot !== rightRoot) {
      const leftScore = scoreMap[leftRoot] || 0;
      const rightScore = scoreMap[rightRoot] || 0;
      // attach lower score to higher score
      if (leftScore >= rightScore) {
        groups[rightRoot] = leftRoot;
      } else {
        groups[leftRoot] = rightRoot;
      }
    }
  }
  return allSuppliers.map((supplier) => ({
    ...supplier,
    group: findRoot(groups, supplier.id),
  }));
}

function findRoot(groups: Record<string, string>, id: string): string {
  if (groups[id] === id) {
    return id;
  }
  const root = findRoot(groups, groups[id]);
  groups[id] = root; // path compression
  return root;
}

function test() {
  // Generate 20 suppliers with increasing scores
  const suppliers = Array.from({ length: 10 }, (_, i) => ({
    id: `supplier-${i + 1}`,
    score: i,
  }));

  // Create some match results
  const results = [
    { left: "supplier-1", right: "supplier-2" },
    { left: "supplier-2", right: "supplier-3" },
    { left: "supplier-4", right: "supplier-5" },
    { left: "supplier-6", right: "supplier-7" },
    { left: "supplier-5", right: "supplier-6" },
    { left: "supplier-8", right: "supplier-9" },
    { left: "supplier-10", right: "supplier-11" },
    { left: "supplier-9", right: "supplier-10" },
  ];

  const grouped = getGroups(suppliers, results);
  console.log(grouped);
}

test();

output:

[
  { id: 'supplier-1', score: 0, group: 'supplier-3' },
  { id: 'supplier-2', score: 1, group: 'supplier-3' },
  { id: 'supplier-3', score: 2, group: 'supplier-3' },
  { id: 'supplier-4', score: 3, group: 'supplier-7' },
  { id: 'supplier-5', score: 4, group: 'supplier-7' },
  { id: 'supplier-6', score: 5, group: 'supplier-7' },
  { id: 'supplier-7', score: 6, group: 'supplier-7' },
  { id: 'supplier-8', score: 7, group: 'supplier-10' },
  { id: 'supplier-9', score: 8, group: 'supplier-10' },
  { id: 'supplier-10', score: 9, group: 'supplier-10' }
]