Motivace: Po světě se toulá spousta agentů. Často se stává, že jeden agent má spoustu jmen/přezdívek, které používá například při rezervaci hotelu, restaurace, na návštěvě u zajímavých osobností. Tato jména si nevolí úplně náhodně, protože na každé jméno musí mít pravé doklady a ty je těžké sehnat. Každý agent má sadu různých jmen a dokladů na ně. Tajná služba postupně odhaluje ekvivalentní jména, tj. jména patřící stejnému agentovi. Tajná služba by ráda používala systém, do kterého si postupně bude ukládat nalezené dvojice ekvivalentních jmen a kterého by se mohla zeptat, jestli je určitá dvojice jmen ekvivalentní.  Například by se chtěli zeptat: “Je agent 007 a James Bond ten samý člověk?”.

Úkol (grafový pohled): Všechna jména agentů odpovídají vrcholům grafu $G=(V,E)$. Dvojice ekvivalentních jmen odpovídá hraně v grafu. Všechny přezdívky jednoho agenta tvoří komponentu souvislosti. Chceme se systému ptát: “Leží vrcholy $u$ a $v$ ve stejné komponentě souvislosti?”. Problému se také někdy říká dynamické udržování komponent souvislosti a nebo problém udržování ekvivalence.

Komponenta souvislosti určená vrcholem $v$ je množina  $C_v=\{u\in V\, |\, \exists\,$cesta z $u$ do $v \}$. V každé komponentě souvislosti vybereme jednoho reprezentanta. Pro jednoduchost budeme reprezentanta komponenty $C_v$ značit $r_v$, takže pokud $u$ a $v$ leží ve stejné komponentě, tak $r_u = r_v$.

Úkol budeme realizovat pomocí operací:

$\FIND(v) = r_v$, operace vrátí reprezentanta komponenty souvislosti $C_v$.

$\UNION(u,v)$ provede sjednocení komponent souvislosti $C_u$ a $C_v$. To odpovídá přidání hrany $uv$ do grafu.

Triviální řešení

Předpokládejme, že vrcholy grafu jsou očíslované čísly $1$ až $n$. Použijeme pole $\ARRAY{R}{1..n}$, kde $\ARRAY{R}{i}=r_i$, tj. číslo reprezentanta komponenty $C_i$. Operace $\FIND$ pouze vypíše $\ARRAY{R}{v}$ a tedy bude trvat $\OO(1)$. K provedení $\UNION(u,v)$ najdeme reprezentanty $r_u = \FIND(u)$, $r_v=\FIND(v)$. Pokud jsou různí, tak projdeme celé pole $\ARRAY{R}{\cdot}$ a každý výskyt $r_u$ přepíšeme na $r_v$. To nám zabere čas $\OO(n)$.

Přehled všech řešení

reprezentace $\FIND{}$ $\UNION{}$
pole $\OO(1)$ $\OO(n)$
pole (union by size) $\OO(1)$ $\OO(n)$
amortiz $\OO(\log n)$
stromečky (union by rank) $\OO(\log n)$ $\OO(\log n)$
stromečky s kompresí $\OO(\log n)$ $\OO(\log n)$
amortiz $\OO(\alpha(n))$ amortiz $\OO(\alpha(n))$

Co se týká implementace, tak jsou všechna řešení natolik jednoduchá, že můžeme vždy naprogramovat nejlepší řešení pomocí stromečků s kompresí cestiček. Dostaneme tak „téměr“ konstantní časovou složitost každé operace.

Upočítání odhadů časové složitosti $\OO(\alpha(n))$ pochází od Tarjana [Tarjan75:unionfind].