U každého reprezentanta $r$ si pamatujeme ještě $\ARRAY{size}{r}= $ # prvků v komponentě $C_r$. A pro každou komponentu si pamatujeme spojový seznam jejich prvků. Seznam lze realizovat jako pole $\ARRAY{next}{\cdot}$ obsahující číslo dalšího prvku v seznamu. Seznam ukončíme nulou. Předchozí řešení pozměníme tak, že v operaci $\UNION{}$ přepíšeme pouze prvky menší komponenty. Díky spojovému seznamu prvků menší komponenty to zvládneme v čase úměrném počtu prvků komponenty. Nakonec zřetězíme seznamy prvků obou komponent a sečteme velikosti komponent.

V nejhorším případě bude operace $\UNION$ trvat opět $\OO(n)$. Ale všimněme si, že prvek $i$ přepisujeme jenom tehdy, když komponentu $C_i$ sjednotíme s druhou komponentou, která má alespoň tolik prvků jako $C_i$. Díku tomu může být každý prvek přepsán nejvýše $(\log n)$-krát. Proto bude $n$ operací $\UNION{}$ dohromady trvat pouze $\OO(n\log n)$. To dává amortizovaný čas pro $\UNION{}$ $\OO(\log n)$.