Predstavme si, že sme vynašli nový spôsob osobnej prepravy, teleport. Je to skutočná revolúcia v cestovaní -- stačí postaviť prepojené teleporty v nejakých dvoch mestách a medzi danými dvoma mestami sa dokážeme presunúť v priebehu pár sekúnd. Ak sa chceme dostať do mesta, kam z nášho mesta priamy teleport nevedie, stačí si nájsť nejaké iné mesto, ktoré je prepojené so štartovným aj cieľovým mestom a ísť cezeň. Prípadne môžeme prestupov použiť viac.
Až tak nás nebudú zaujímať detaily optimálnej cesty (stačí nám vedieť, že je veľmi rýchla). Povedzme, že nám stačí vedieť, či sa vieme medzi dvoma destináciami pomocou teleportov vôbec dostať.
Na zistenie, odkiaľ kam sa vieme dostať, nám stačí rozdeliť si graf na komponenty súvislosti. To vieme pomocou obyčajného DFS alebo DFS -- prejdeme si v cykle všetky vrcholy, a pre každý, ktorý zatiaľ nemá priradené číslo komponentu, mu priradíme nové číslo (ktoré potom zväčšíme) a spustíme z daného vrcholu prehľadávanie. Všetkým vrcholom, ktoré pri prehľadávaní navštívime, nastavíme rovnaké číslo komponentu.
Keď sa potom pýtame na prepojenosť dvoch miest, stačí overiť, či majú rovnaké číslo komponentu.
Teraz si ale predstavme, že veľa dvojíc miest po celej krajine si postupne stavia ďalšie a ďalšie prepojenia.
Občas sa nás niekto spýta, či sa medzi nejakou dvojicou miest dá pomocou teleportov dostať. A občas sa teda dozvieme, že ďalšia dvojica miest bola spojená teleportom. Pokiaľ tieto mestá doposiaľ dosiahnuteľné neboli, naše informácie o prepojenosti miest už nie sú aktuálne a treba ich prepočítať.
Keď si to sformalizujeme, tak naša sieť miest zodpovedá niekoľkým množinám. V jednej množine sú všetky mestá, ktoré sa dajú navštíviť sériou teleportácií. Zároveň máme dve operácie, ktoré s našimi množinami robíme:
V podstate máme dve jednoduché možnosti, čo robiť. Nech máme $N$ miest, $U$ operácií union (zjednotenie, spojenie miest) a $Q$ operácií find (otázok).
Pokiaľ je počet nových zjednotení $U$ malý, možeme si pri každom novom zjednotení komponenty súvislosti prepočítať odznova. To je pracné, pretože prejsť všetky vrcholy trvá až $O(N)$ času. Odpovedanie na otázky je ale veľmi rýchle, len zistíme, či je číslo komponentu pre obe mestá rovnaké. Toto riešenie má teda časovú zložitosť $O(UN + Q)$. Počet zjednotení vieme obmedziť tým, že pred každým z nich skontrolujeme, či už dva spájané vrcholy neležia v tej istej množine. Ak áno, nemusíme ich spájať. V takom príapde môže byť zjednotení najviac $O(N)$, časová zložitosť je preto $O(N^2 + Q)$.
Pokiaľ je naopak počet otázok $Q$ malý, môžeme úplne ignorovať predpočítavanie komponentov súvislosti. Stačí nám pri operácií pridávať hrany do štandardne reprezentovaného grafu miest. Otázku potom zodpovieme tak, že spustíme prehľadávanie grafu (DFS alebo BFS) z jedného z vrcholov a pokiaľ sa nám podarí nájsť ten druhý, sú spojené. Toto riešenie má časovú zložitosť $(U + NQ)$.
Určite vidíme, že pokiaľ máme veľké množstvo zjednotení aj otázok, potrebujeme niečo efektívnejšie.