Ponekad je u programu potrebno održavati nekoliko disjunktnih skupova (često podskupova nekog skupa), pri čemu je potrebno umeti za dati element efikasno pronaći kom skupu pripada (tu operaciju zovemo find tj. pronadji) i efikasno spojiti dva zadata skupa u novi, veći skup (tu operaciju zovemo union tj. unija). Pretpostavićemo da je svaki skup jednoznačno određen nekom oznakom (to može biti redni broj skupa, naziv skupa ili neki kanonski predstavnik skupa). Argumenti operacije unija ne moraju biti oznake skupova čiju uniju treba kreirati, već mogu biti proizvoljni elementi tih skupova. Prilikom izvođenja unije polazni skupovi se uklanjaju iz kolekcije, i u kolekciju se dodaje njihova unija.
Problem. Definisati strukture podataka koje omogućavaju sledeći interfejs:
pronadji(x) – vraća oznaku skupa kom pripada element x (ta oznaka može biti ili neki brojevni identifikator ili neki kanonski predstavnik tog skupa);unija(x, y) – spaja skup koji sadrži element x i skup koji sadrži element y.Pomoću operacije pronadji lako možemo za dva elementa proveriti da li pripadaju istom skupu tako što za svaki od njih pronađemo oznaku skupa kom pripada i proverimo da li su ove oznake jednake.
Razmotrimo situaciju u kojoj nekom događaju prisustvuje \(n\) osoba. Reći čemo da se dve osobe poznaju ako se poznaju direktno ili indirektno. Naime, ako se osobe \(A\) i \(B\) poznaju, i osobe \(B\) i \(C\) se poznaju, onda zaključujemo da se i osobe \(A\) i \(C\) poznaju. Želimo da osmislimo strukturu podataka kojom je moguće za proizvoljne dve osobe utvrditi da li se poznaju ili ne, i koja omogućava sklapanje novih poznanstava, tj. kojom se prilikom upoznavanja dve nove osobe, efikasno ažurira relacija poznanstva.
Primetimo da je ovakva struktura podataka korisna kada god radimo sa nekim relacijama ekvivalencije i kada je potrebno predstaviti klase ekvivalencije (koje su disjunktni podskupovi skupa na kom je relacija definisana). Provera da li su dva elementa u relaciji se zasniva na proveri da li pripadaju istoj klasi, a uspostavljanje relacije između bilo koja dva elementa dovodi do spajanja njihovih klasa ekvivalencije. Često se upotrebljava za analizu povezanosti nekih elemenata. Na primer, korisnici društvenih mreža se mogu grupisati u klase ekvivalencije na osnovu svojih poznanstava sa drugim korisnicima i korišćenjem ovakve strukture podataka možemo lako utvrditi da li su svi međusobno povezani (preko zajedničkih poznanika).
Struktura podataka koja podržava ovakav interfejs se često naziva union-find ili DSU (engl. disjoint set union), pri čemu se pod tim imenom obično podrazumeva i specifična, efikasna implementacija (pre nje, u nastavku ćemo prikazati i jednostavniju, ali neefikasniju implementaciju).
Strukture podataka za rad sa disjunktnim skupovima imaju različite primene. Jedna od najznačajnijih je održavanje komponenti povezanosti u Kruskalovom algoritmu za konstrukciju minimalnog povezujućeg drveta u grafu. Mogu se koristiti i za segmentaciju slika, tj. particionisanje slike na veći broj disjunktnih regiona, tako da su svi pikseli istog regiona slični u pogledu nekog svojstva kao što je boja, intenzitet ili tekstura.
Jedna moguća implementacija strukture podataka sa ovakvim interfejsom podrazumeva da se održava preslikavanje svakog elementa u oznaku skupa kojem pripada. Ako pretpostavimo da razmatramo skup od \(n\) elemenata i da su svi elementi numerisani brojevima od \(0\) do \(n-1\), onda ovo preslikavanje možemo realizovati pomoću običnog niza gde se na poziciji svakog elementa nalazi oznaka skupa kojem on pripada (ukoliko elementi nisu numerisani brojevima, možemo umesto niza da koristimo mapu kojom se oznake elemenata preslikavaju u oznake skupa kom element pripada). Primer takve reprezentacije prikazan je na slici 1.
Operacija pronadji je tada trivijalna: dovoljno je iz niza pročitati oznaku skupa kom element pripada. Složenost operacije pronadji je tada \(O(1)\).
Operacija unija je mnogo sporija jer podrazumeva da se oznake svih elemenata jednog skupa menjaju u oznake drugog, što zahteva da se prođe kroz ceo niz. Složenost operacije unija je tada \(\Theta(n)\).
Ukoliko bi se umesto niza koristila neuređena mapa i ako bismo pretpostavili da je složenost operacija sa mapom \(O(1)\) (što je zaista amortizovana složenost operacija nad neuređenom mapom), operacija pronadji bila bi složenosti \(O(1)\) a operacija unija složenosti \(O(n)\) (jer je ponekad potrebno menjati oznake skupova za sve elemente). Kako bismo odredili amortizovanu složenost (što je relevantno za ocenu složenosti efikasnijih implementacija, koje ćemo kasnije opisati), potrebno je da procenimo potrebno vreme izvršavanja \(m\) operacija od kojih je svaka tipa unija ili pronadji. Najgori slučaj za ukupno vreme izvršavanja ovog niza operacija možemo da ocenimo kao \(O(m\cdot n)\), jer iako se operacija pronadji izvršava veoma efikasno – u vremenu \(O(1)\), složenost operacije unija je linearna u odnosu na broj elemenata koji održavamo i najgori slučaj nastupa kada stalno vršimo unije (doduše, maksimalni broj izvršavanja operacije unije različitih skupova je \(n-1\), jer će se nakon toga svi elementi objediniti u isti skup, pa je ukupno vreme svih tih operacija reda \(O(n^2)\)).
Primer 1.3.1. Ilustrujmo sprovođenje operacija pronadji i unija nad opisanom implementacijom strukture podataka za disjunktne skupove na jednom primeru. Pretpostavimo da je početno stanje takvo da svaki element pripada zasebnom skupu. Razmotrimo na koji način se menja sadržaj odgovarajućeg niza nakon izvršavanja operacija unije. Izvršavanje nekoliko operacija unije prikazano je na slici 2. Levo su prikazani skupovi, a desno niz kojim su ti skupovi predstavljeni (iznad svakog niza prikazani su indeksi). Pretpostavljamo da će prilikom izvršavanja operacije unija(x,y) oznaka novog skupa biti oznaka skupa kojem pripada element y.
Prikažimo sada implementaciju ove tehnike (jednostavnosti radi koristimo globalne promenljive).
int id[MAX_N];
int n;
// na pocetku svaki element pripada zasebnom skupu
void inicijalizuj() {
for (int i = 0; i < n; i++)
id[i] = i;
}
// oznaku podskupa kome pripada element x citamo sa pozicije x iz niza
int pronadji(int x) {
return id[x];
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int idx = id[x], idy = id[y];
// oznake svih elemenata prvog podskupa menjamo u oznaku drugog podskupa
for (int i = 0; i < n; i++)
if (id[i] == idx)
id[i] = idy;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
#include <iostream>
using namespace std;
const int MAX_N = 1e5;
int id[MAX_N];
int n;
// na pocetku svaki element pripada zasebnom skupu
void inicijalizuj() {
for (int i = 0; i < n; i++)
id[i] = i;
}
// oznaku podskupa kome pripada element x citamo sa pozicije x iz niza
int pronadji(int x) {
return id[x];
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int idx = id[x], idy = id[y];
// oznake svih elemenata prvog podskupa menjamo u oznaku drugog podskupa
for (int i = 0; i < n; i++)
if (id[i] == idx)
id[i] = idy;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
inicijalizuj();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char vrsta_upita;
cin >> ws >> vrsta_upita;
if (vrsta_upita == 'u') {
int x, y;
cin >> x >> y;
unija(x, y);
} else if (vrsta_upita == 'p') {
int x, y;
cin >> x >> y;
cout << (u_istom_podskupu(x, y) ? "da" : "ne") << "\n";
}
}
return 0;
}Obratimo pažnju da se prilikom izvođenja unije moraju koristiti pomoćne promenljive (razmislite zašto je naredna implementacija neispravna).
// pravimo uniju skupova kome pripadaju dati elementi
void unija(int x, int y) {
// oznake svih elemenata prvog skupa menjamo u oznaku drugog skupa
for (int i = 0; i < n; i++)
if (id[i] == id[x])
id[i] = id[y];
}Razmotrimo nešto drugačiju implementaciju ove strukture podataka u kojoj je operacija unija vremenski efikasnija.
Ključna ideja na kojoj se zasniva efikasnije rešenje je da elemente ne preslikavamo u oznake skupova, već da skupove čuvamo u obliku drveta (ne nužno binarnih) tako da svaki element slikamo u njegovog roditelja u drvetu. Svaki koren drveta slikamo samog u sebe i smatramo ga predstavnikom skupa predstavljenog tim drvetom (dakle, predstavnik svakog skupa je koren njegovog drveta). Naglasimo da su u čvorovima ovih drveta pokazivači usmereni od dece ka roditeljima, za razliku od klasičnih drveta gde pokazivači u čvorovima ukazuju od roditelja ka deci.
Da bismo za proizvoljni element saznali oznaku skupa kom pripada tj. da bismo implementirali operaciju pronadji, potrebno je da počev od tog elementa prođemo kroz niz roditeljskih čvorova sve dok ne stignemo do korena. Uniju dva skupa (tj. operaciju unija) u ovom pristupu možemo jednostavno realizovati tako što koren jednog drveta usmerimo ka korenu drugog.
Naivna implementacija koja je opisana u prethodnom poglavlju odgovara situaciji u kojoj osoba koja promeni adresu obaveštava sve druge osobe o svojoj novoj adresi, dok implementacija koju trenutno opisujemo odgovara scenariju u kome samo na staroj adresi ostavlja informaciju o svojoj novoj adresi. Ovo, naravno, malo usporava dostavu pošte, jer se mora preći kroz niz preusmeravanja, ali ako taj niz nije predugačak, može biti značajno efikasnije od prvog pristupa.
Primer 1.3.2. Prikažimo rad algoritma na jednom primeru. Skupove ćemo predstavljati drvetima.
Pretpostavljamo da su na početku svi skupovi jednočlani.
unija(1, 0). Predstavnik skupa kome pripada \(1\) je \(1\) i čvor koji sadrži \(1\) preusmeravamo tako da ukazuje na čvor predstavnika skupa u kome je \(0\), a to je \(0\).
unija(6, 5). Predstavnik skupa kome pripada \(6\) je \(6\) i čvor koji sadrži \(6\) preusmeravamo tako da ukazuje na čvor koji sadrži predstavnika skupa u kome je \(5\), a to je \(5\).
unija(3, 6). Predstavnik skupa kome pripada \(3\) je \(3\) i čvor koji sadrži \(3\) preusmeravamo tako da ukazuje na čvor koji sadrži predstavnika skupa u kome je \(6\), a to je \(5\).
unija(4, 7). Predstavnik skupa kome pripada \(4\) je \(4\) i čvor koji sadrži \(4\) preusmeravamo tako da ukazuje na čvor koji sadrži predstavnika skupa u kome je \(7\), a to je \(7\).
unija(2, 0). Predstavnik skupa kome pripada \(2\) je \(2\) i čvor koji sadrži \(2\) preusmeravamo tako da ukazuje na čvor koji sadrži predstavnika skupa u kome je \(0\), a to je \(0\).
unija(4, 3). Predstavnik skupa kome pripada \(4\) je \(7\) i čvor koji sadrži \(7\) preusmeravamo tako da ukazuje na čvor koji sadrži predstavnika skupa u kome je \(3\), a to je \(5\).
unija(2, 6). Predstavnik skupa kome pripada \(2\) je \(0\) i čvor koji sadrži \(0\) preusmeravamo tako da ukazuje na čvor koji sadrži predstavnika skupa u kome je \(6\), a to je \(5\).
Iako ovako opisana struktura podataka ima drvoliku strukturu, možemo je implementirati korišćenjem statičkog niza. Naime, pošto svaki element u drvetu ima jedinstvenog roditelja, na poziciji nekog elementa u nizu možemo čuvati indeks njegovog roditelja. U slučaju da je element koren nekog drveta, njegov roditelj je on sâm.
Primer 1.3.3. Za drvo iz prethodnog primera, niz roditelja ima sledeći sadržaj:
Imajući u vidu ovakvu reprezentaciju, kôd je prilično jednostavno napisati (jednostavnosti radi pretpostavljamo da se podaci smeštaju u globalnim promenljivim).
int roditelj[MAX_N];
int n;
// na pocetku svaki element pripada zasebnom skupu
void inicijalizuj() {
for (int i = 0; i < n; i++)
roditelj[i] = i;
}
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
// sve dok ne stignemo do korena
while (roditelj[x] != x)
// penjemo se u roditeljski cvor
x = roditelj[x];
return x;
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// postavljamo da je koren prvog podskupa sin korena drugog podskupa
roditelj[fx] = fy;
}#include <iostream>
using namespace std;
const int MAX_N = 1e5;
int roditelj[MAX_N];
int n;
// na pocetku svaki element pripada zasebnom skupu
void inicijalizuj() {
for (int i = 0; i < n; i++)
roditelj[i] = i;
}
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
// sve dok ne stignemo do korena
while (roditelj[x] != x)
// penjemo se u roditeljski cvor
x = roditelj[x];
return x;
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// postavljamo da je koren prvog podskupa sin korena drugog podskupa
roditelj[fx] = fy;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
int main() {
cin >> n;
inicijalizuj();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char vrsta_upita;
cin >> ws >> vrsta_upita;
if (vrsta_upita == 'u') {
int x, y;
cin >> x >> y;
unija(x, y);
} else if (vrsta_upita == 'p') {
int x, y;
cin >> x >> y;
cout << (u_istom_podskupu(x, y) ? "da" : "ne") << endl;
}
}
return 0;
}Složenost prethodnog pristupa zavisi od toga koliko su drveta kojima se predstavljaju skupovi uravnotežena1. U najgorem slučaju se drveta mogu izdegenerisati u liste i tada je složenost najgoreg slučaja svake od operacija unija i pronadji \(O(n)\).
Primer 1.3.4. Ako uvek prilikom izvršavanja operacije unija(x,y) usmeravamo pokazivač od predstavnika skupa kojem pripada element \(x\) ka predstavniku skupa kojem pripada element \(y\), izvršiće se niz izmena drveta koji je prikazan na slici 3. Upit kojim se traži predstavnik skupa kojem pripada element 4 se realizuje nizom koraka kojima se prelazi preko elemenata 3, 2, 1, 0 i u slučaju većeg broja elemenata se dobija veoma neefikasna implementacija pronalaženja predstavnika (a samim tim i unije, čija implementacija podrazumeva pronalaženje predstavnika).
Trenutni algoritam, dakle, nije u najgorem slučaju (ilustrovanom na slici 3) efikasniji od naivnog pristupa. Naime, u naivnom pristupu se pronalaženje predstavnika vrši u vremenu \(O(1)\), ali unija uvek zahteva vreme \(O(n)\), dok ovde i operacija pronadji može imati složenost \(O(n)\). Ipak, složenost trenutnog algoritma se može popraviti ako se sve vreme drveta održavaju uravnoteženim. Kada su drveta uravnotežena, možemo dokazati da je složenost najgoreg slučaja svake od operacija unija i pronadji jednaka \(O(\log{n})\). Na ovaj način se postiže da je vreme izvršavanja niza od \(m\) operacija tipa unija ili pronadji u najgorem slučaju jednako \(O(m\log n)\), dok je u naivnom pristupu vreme izvršavanja ovog niza operacija, u slučaju kada je broj operacija tipa unija \(O(m)\), jednako \(O(mn)\).
Prilikom pravljenja unije imamo slobodu izbora korena kog ćemo usmeriti prema drugom korenu i uravnoteženost se postiže time što se ova sloboda na neki način iskoristi. Postoje dva uobičajena načina vršenja unije: unija na osnovu ranga (visine) i unija na osnovu broja elemenata (veličine).
Osnovna ideja vršenja unije na osnovu ranga (visine) je da se prilikom izmena (a one se vrše samo u sklopu operacije unije), ako je moguće, obezbedi da se visina2 drveta kojim je predstavljena unija ne poveća u odnosu na visine pojedinačnih drveta koja predstavljaju skupove čija se unija pravi. Pretpostavićemo da svakom čvoru drveta pridružujemo broj koji predstavlja visinu tog čvora tj. drveta sa korenom u tom čvoru. Visinu drveta možemo održavati u posebnom nizu (njega ćemo u kodu, nazvati rang3). Ako se uvek izabere da koren drveta manje visine usmeravamo ka korenu drveta veće ili jednake visine, tada se visina unije povećava samo ako su oba drveta koja uniramo iste visine.
int roditelj[MAX_N];
int n;
int rang[MAX_N];
// na pocetku svaki element pripada zasebnom skupu
// i visina svakog drveta je 0
void inicijalizuj() {
for (int i = 0; i < n; i++) {
roditelj[i] = i;
rang[i] = 0;
}
}
// pravimo uniju podskupova kojima pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// usmeravamo koren drveta nizeg ka korenu viseg ranga
if (rang[fx] < rang[fy])
swap(fx, fy);
roditelj[fy] = fx;
// ako su podskupovi istog ranga
// unija ce biti za jedan veceg ranga
if (rang[fx] == rang[fy])
rang[fx]++;
}#include <iostream>
using namespace std;
const int MAX_N = 1e5;
int roditelj[MAX_N];
int n;
int rang[MAX_N];
// na pocetku svaki element pripada zasebnom skupu
// i visina svakog drveta je 0
void inicijalizuj() {
for (int i = 0; i < n; i++) {
roditelj[i] = i;
rang[i] = 0;
}
}
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
// sve dok ne stignemo do korena
while (roditelj[x] != x)
// penjemo se u roditeljski čvor
x = roditelj[x];
return x;
}
// pravimo uniju podskupova kojima pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// usmeravamo koren drveta nizeg ka korenu viseg ranga
if (rang[fx] < rang[fy])
swap(fx, fy);
roditelj[fy] = fx;
// ako su podskupovi istog ranga
// unija ce biti za jedan veceg ranga
if (rang[fx] == rang[fy])
rang[fx]++;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
inicijalizuj();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char vrsta_upita;
cin >> ws >> vrsta_upita;
if (vrsta_upita == 'u') {
int x, y;
cin >> x >> y;
unija(x, y);
} else if (vrsta_upita == 'p') {
int x, y;
cin >> x >> y;
cout << (u_istom_podskupu(x, y) ? "da" : "ne") << "\n";
}
}
return 0;
}Primetimo da su nam za izvođenje operacije unije relevantne samo vrednosti ranga predstavnika skupova.
Dokažimo lemu koja garantuje složenost.
Lema 1.3.1. [Uniranje na osnovu ranga daje uravnotežena drveta] U slučaju vršenja unije na osnovu ranga, u svakom drvetu čiji je rang \(h\) nalazi se bar \(2^h\) čvorova.
Dokaz. Tvrđenje dokazujemo matematičkom indukcijom.
Baza indukcije odgovara polaznom stanju u kome je svaki čvor svoj predstavnik. Rangovi svih drveta su tada nula i sva drveta imaju \(2^0 = 1\) čvor, pa tvrđenje važi.
Pokažimo da operacija unije održava ovu invarijantu. Po induktivnoj hipotezi znamo da ako dva drveta koja predstavljaju skupove koji se uniraju imaju rangove \(r_1\) i \(r_2\), onda je broj čvorova u njima redom bar \(2^{r_1}\) i \(2^{r_2}\) čvorova. Ukoliko se uniranjem rang ne poveća, invarijanta je trivijalno očuvana jer se broj čvorova uvećao, a rang je ostao isti. Jedini slučaj kada se uniranjem povećava rang je kada je \(r_1 = r_2\) i tada unirano drvo ima rang \(r = r_1 + 1 = r_2 + 1\) i bar \(2^{r_1} + 2^{r_2} = 2^{r_1} + 2^{r_1} = 2\cdot 2^{r_1} = 2^{r_1+1} = 2^r\) čvorova.
Time je tvrđenje dokazano. \(\Box\)
Dakle, rang (visina) svakog drveta koje ima \(n\) čvorova je \(O(\log{n})\), pa je složenost operacije pronalaženja predstavnika u skupu od \(n\) čvorova reda \(O(\log{n})\). Pošto uniranje nakon pronalaženja predstavnika vrši još samo \(O(1)\) operacija, i složenost uniranja dva skupa je \(O(\log{n})\).
Dakle, održavanje visina skupova pod kontrolom nam garantuje logaritamsku složenost osnovnih operacija i vreme izvršavanja niza od \(m\) operacija od kojih je svaka tipa unija ili pronadji je u najgorem slučaju jednako \(O(m\log n)\).
U pristupu Unija na osnovu broja elemenata (veličine), umesto visine se u svakom od skupova održava broj čvorova tog skupa (tj. u svakom čvoru drveta čuva se informacija o broju čvorova drveta kojem je taj čvor koren).
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// usmeravamo koren manjeg drveta kao korenu veceg drveta
if (velicina[fx] < velicina[fy])
swap(fx, fy);
roditelj[fy] = fx;
// azuriramo velicinu novog korena
velicina[fx] += velicina[fy];
}#include <iostream>
using namespace std;
const int MAX_N = 1e5;
int roditelj[MAX_N];
int n;
int velicina[MAX_N];
// na pocetku svaki element pripada zasebnom skupu
// i visina svakog drveta je 0
void inicijalizuj() {
for (int i = 0; i < n; i++) {
roditelj[i] = i;
velicina[i] = 1;
}
}
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
// penjemo se do korena tako sto preskacemo po jedan cvor
while (x != roditelj[x])
x = roditelj[x];
return x;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// usmeravamo koren manjeg drveta kao korenu veceg drveta
if (velicina[fx] < velicina[fy])
swap(fx, fy);
roditelj[fy] = fx;
// azuriramo velicinu novog korena
velicina[fx] += velicina[fy];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
inicijalizuj();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char vrsta_upita;
cin >> ws >> vrsta_upita;
if (vrsta_upita == 'u') {
int x, y;
cin >> x >> y;
unija(x, y);
} else if (vrsta_upita == 'p') {
int x, y;
cin >> x >> y;
cout << (u_istom_podskupu(x, y) ? "da" : "ne") << "\n";
}
}
return 0;
}Ako uvek usmeravamo predstavnika skupa sa manjim brojem elemenata ka predstavniku skupa sa većim brojem elemenata, ponovo dobijamo logaritamsku složenost najgoreg slučaja za obe osnovne operacije. Ovo važi zato što i ovaj način pravljenja unije garantuje da ne možemo imati visoko drvo sa malim brojem čvorova. Naime, da bi se dobilo drvo visine 1, potrebna su bar dva drveta visine \(0\), odnosno bar \(2\) čvora; da bi se dobilo drvo visine \(2\) potrebna su bar dva drveta visine \(1\) koja imaju bar po \(2\) čvora, odnosno drvo visine \(2\) ima bar \(4\) čvora. Analogno prethodnoj, moguće je dokazati i narednu lemu.
Lema 1.3.2. [Uniranje na osnovu broja elemenata daje uravnotežena drveta] U slučaju vršenja unije na osnovu broja elemenata, u svakom drvetu čija je visina \(h\) nalazi se bar \(2^h\) čvorova tj. za svaki koren drveta \(r\) visine \(h\) sa \(s\) čvorova važi \(s \geq 2^h\).
Dokaz. Dokažimo lemu indukcijom.
U početku je broj čvorova u svakom drvetu \(s=1\), a visina svakog drveta je \(h=0\), pa važi \(s=2^h\).
Pretpostavimo da tvrđenje važi pre spajanja dva drveta čiji su koreni \(r_1\) i \(r_2\), koji imaju redom \(s_1\) i \(s_2\) elemenata, visine \(h_1\) i \(h_2\). Na osnovu induktivne hipoteze znamo da je \(s_1 \geq 2^{h_1}\) i \(s_2 \geq 2^{h_2}\). Pretpostavimo da se drvo \(r_2\) pridružuje drvetu \(r_1\) (što znači da drvo sa korenom \(r_2\) ima manje ili jednako čvorova nego ono sa korenom \(r_1\) tj. da je \(s_2 \leq s_1\)), čime se dobija drvo sa \(s\) čvorova visine \(h\).
Ako drvo sa korenom \(r_1\) ima veću visinu od onog sa korenom \(r_2\), tj ako je \(h_1 > h_2\), nakon spajanja se visina drveta sa korenom \(r_1\) ne manja, a broj čvorova mu se povećava, pa tvrđenje leme trivijalno nastavlja da važi. Zaista, važi \(s = s_1 + s_2 \geq s_1 \geq 2^{h_1} = 2^h\).
U suprotnom se visina drveta sa korenom drveta \(r_1\) povećava i postaje za jedan veća od visine drveta sa korenom \(r_2\) tj. važi \(h = h_2 + 1\). Tada važi \(s = s_1 + s_2 \geq 2\cdot s_2 \geq 2\cdot 2^{h_2} = 2^{h_2 + 1} = 2^h\). \(\Box\)
Odavde sledi da su visine svih drveta u ovoj strukturi podataka reda \(O(\log n)\).
U narednom apletu možete isprobati kako radi operacija unije.
Iako je složenost prethodno opisanih varijanti algoritma sasvim prihvatljiva (složenost izvršavanja \(m\) operacija unije je \(O(m\log{n})\)), može se dodatno poboljšati veoma jednostavnom tehnikom poznatom kao sažimanje puteva ili kompresija puteva (engl. path compression). Naime, prilikom pronalaženja predstavnika možemo sve čvorove kroz koje prolazimo usmeriti ka korenu. Primetimo da tada pored operacije unija i operacija pronadji menja strukturu drveta kojim je predstavljen taj skup. Jedan način da se to uradi je da se nakon pronalaženja korena, ponovo prođe kroz niz elemenata i svi pokazivači usmere ka korenu (slika 4). Na ovaj način se postiže da buduće operacije nad tim skupom budu efikasnije.
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
int koren = x;
// nalazimo oznaku podskupa kao koreni element podskupa
while (koren != roditelj[koren])
koren = roditelj[koren];
// svim cvorovima na putanji od x do korena
// postavljamo da je roditeljski cvor koren tog podskupa
while (x != koren) {
int tmp = roditelj[x];
roditelj[x] = koren;
x = tmp;
}
return koren;
}#include <iostream>
using namespace std;
const int MAX_N = 1e5;
int roditelj[MAX_N];
int n;
int rang[MAX_N];
// na pocetku svaki element pripada zasebnom skupu
// i visina svakog drveta je 0
void inicijalizuj() {
for (int i = 0; i < n; i++) {
roditelj[i] = i;
rang[i] = 0;
}
}
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
int koren = x;
// nalazimo oznaku podskupa kao koreni element podskupa
while (koren != roditelj[koren])
koren = roditelj[koren];
// svim cvorovima na putanji od x do korena
// postavljamo da je roditeljski cvor koren tog podskupa
while (x != koren) {
int tmp = roditelj[x];
roditelj[x] = koren;
x = tmp;
}
return koren;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// usmeravamo koren nizeg drveta kao korenu viseg drveta
if (rang[fx] < rang[fy])
swap(fx, fy);
roditelj[fy] = fx;
// ako su podskupovi istog ranga
// unija ce biti za jedan veceg ranga
if (rang[fx] == rang[fy])
rang[fx]++;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
inicijalizuj();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char vrsta_upita;
cin >> ws >> vrsta_upita;
if (vrsta_upita == 'u') {
int x, y;
cin >> x >> y;
unija(x, y);
} else if (vrsta_upita == 'p') {
int x, y;
cin >> x >> y;
cout << (u_istom_podskupu(x, y) ? "da" : "ne") << "\n";
}
}
return 0;
}Za sve čvorove koji se obilaze od polaznog čvora do korena, dužine putanja do korena se nakon ovoga smanjuju na 1; slično, skraćuju se i putanje do korena svih čvorova u poddrvetu sa korenom u polaznom čvoru. Ako se vrši uniranje na osnovu broja elemenata, prilikom sažimanja puteva ne menjaju se brojevi elemenata drveta, pa podaci pridruženi čvorovima ostaju korektni i nakon sažimanja puteva. Ako pak vršimo uniju na osnovu ranga, i tumačimo rangove kao visine drveta, jasno je da prilikom sažimanja puteva niz rangova postaje neažuran (jer se neke visine smanjuju, a niz se ne ažurira). Interesantno je da ni u ovom slučaju nema potrebe da se niz ažurira. Naime, rangovi tj. brojevi koji se čuvaju u tom nizu ne predstavljaju više visine čvorova (zato niz nismo ni nazvali visine), već gornje granice visina čvorova tj. visine čvorova su manje ili jednake od tih vrednosti. Ovi brojevi nam pomažu da preusmerimo čvorove prilikom uniranja. Lako se pokazuje da se ovim ne narušava složenost najgoreg slučaja i da funkcija nastavlja korektno da radi. Naime, i dalje važi osnovna invarijanta garantovana lemom 1.3.1 da se u svakom drvetu koje ima rang \(h\) nalazi bar \(2^h\) čvorova, a pošto je visina manja ili jednaka od ranga, važi da je visina svakog drveta koje sadrži \(n\) čvorova najviše \(\log{n}\).
U prethodnoj implementaciji funkcije pronadji se dva puta prolazi kroz putanju od čvora \(x\) do korena. Slične performanse se mogu dobiti i u samo jednom prolazu. Postoje dva načina na koji se ovo može uraditi: jedan od njih je da se svaki čvor kroz koji se prolazi tokom pronalaženja predstavnika (osim deteta korena) usmeri ka roditelju svog roditelja. Za sve čvorove koji se obilaze (na putu od polaznog čvora do korena), dužine putanja do korena se nakon ovoga smanjuju dvostruko (slika 5, sredina), što je dovoljno za odlične performanse.
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
int tmp;
// za sve cvorove na putanji od x do korena
while (x != roditelj[x]) {
tmp = roditelj[x];
// novi roditelj od x je roditelj njegovog roditelja
roditelj[x] = roditelj[roditelj[x]];
x = tmp;
}
return x;
}#include <iostream>
using namespace std;
const int MAX_N = 1e5;
int roditelj[MAX_N];
int n;
int rang[MAX_N];
// na pocetku svaki element pripada zasebnom skupu
// i visina svakog drveta je 0
void inicijalizuj() {
for (int i = 0; i < n; i++) {
roditelj[i] = i;
rang[i] = 0;
}
}
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
int tmp;
// za sve cvorove na putanji od x do korena
while (x != roditelj[x]) {
tmp = roditelj[x];
// novi roditelj od x je roditelj njegovog roditelja
roditelj[x] = roditelj[roditelj[x]];
x = tmp;
}
return x;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// usmeravamo koren nizeg drveta kao korenu viseg drveta
if (rang[fx] < rang[fy])
swap(fx, fy);
roditelj[fy] = fx;
// ako su podskupovi istog ranga
// unija ce biti za jedan veceg ranga
if (rang[fx] == rang[fy])
rang[fx]++;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
inicijalizuj();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char vrsta_upita;
cin >> ws >> vrsta_upita;
if (vrsta_upita == 'u') {
int x, y;
cin >> x >> y;
unija(x, y);
} else if (vrsta_upita == 'p') {
int x, y;
cin >> x >> y;
cout << (u_istom_podskupu(x, y) ? "da" : "ne") << "\n";
}
}
return 0;
}Drugi način podrazumeva da se, prilikom prolaska od čvora ka korenu, svaki drugi čvor na putanji usmeri ka roditelju svog roditelja (slika 5, desno).
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
// penjemo se do korena tako sto preskacemo po jedan cvor
while (x != roditelj[x]) {
// novi roditelj od x je roditelj njegovog roditelja
roditelj[x] = roditelj[roditelj[x]];
x = roditelj[x];
}
return x;
}#include <iostream>
using namespace std;
const int MAX_N = 1e5;
int roditelj[MAX_N];
int n;
int rang[MAX_N];
// na pocetku svaki element pripada zasebnom skupu
// i visina svakog drveta je 0
void inicijalizuj() {
for (int i = 0; i < n; i++) {
roditelj[i] = i;
rang[i] = 0;
}
}
// naziv podskupa kome element pripada dobijamo kao oznaku korena tog podskupa
int pronadji(int x) {
// penjemo se do korena tako sto preskacemo po jedan cvor
while (x != roditelj[x]) {
// novi roditelj od x je roditelj njegovog roditelja
roditelj[x] = roditelj[roditelj[x]];
x = roditelj[x];
}
return x;
}
// elementi su u istom podskupu ako su im oznake iste
int u_istom_podskupu(int x, int y) {
return pronadji(x) == pronadji(y);
}
// pravimo uniju podskupova kome pripadaju dati elementi
void unija(int x, int y) {
int fx = pronadji(x), fy = pronadji(y);
// x i y imaju istog predstavnika, pa su vec u istom podskupu
if (fx == fy)
return;
// usmeravamo koren nizeg drveta kao korenu viseg drveta
if (rang[fx] < rang[fy])
swap(fx, fy);
roditelj[fy] = fx;
// ako su podskupovi istog ranga
// unija ce biti za jedan veceg ranga
if (rang[fx] == rang[fy])
rang[fx]++;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n;
inicijalizuj();
int q;
cin >> q;
for (int i = 0; i < q; i++) {
char vrsta_upita;
cin >> ws >> vrsta_upita;
if (vrsta_upita == 'u') {
int x, y;
cin >> x >> y;
unija(x, y);
} else if (vrsta_upita == 'p') {
int x, y;
cin >> x >> y;
cout << (u_istom_podskupu(x, y) ? "da" : "ne") << "\n";
}
}
return 0;
}
Primetimo da je na ovaj način dodata samo jedna linija koda u prvobitnu implementaciju operacije pronadji.
Kada se primeni bilo koji od tri navedena oblika sažimanja puteva, amortizovana složenost operacija postaje samo \(O(\alpha(n))\) (što ovde nećemo dokazivati), gde je \(\alpha(n)\) takozvana inverzna Akermanova funkcija koja jako sporo raste4. Za bilo koji broj \(n\) koji je manji od broja atoma u celom univerzumu (oko \(10^{80}\)) važi da je \(\alpha(n) < 5\), tako da je amortizovana vremenska složenost operacija praktično konstantna.
Zadaci:
Pojam uravnoteženog drveta može se precizno definisati na razne načine. U ovom tekstu ćemo uravnoteženost razmatrati samo neformalno: drvo smatramo uravnoteženijim što je rastojanje listova od korena ujednačenije.↩︎
Visinu čvora možemo definisati kao broj grana na putanji od tog čvora do njemu najudaljenijeg lista. Visinu drveta računamo kao visinu njegovog korena.↩︎
U poglavlju 1.3.2.3 posvećenom sažimanju puteva, videćemo da kada se vrše optimizacije ovaj niz ne čuva više visinu svakog drveta već rang (engl. rank) koji predstavlja gornju granicu visine tj. broj od kog ta visini sigurno nije veća.↩︎
Akermanova funkcija je poznata po tome što jako brzo raste. Ona je definisana rekurentnim relacijama: \(A(0, n) = n+1\), \(A(m+1, 0) = A(m, 1)\), \(A(m+1, n+1) = A(m, A(m+1, n))\). Funkcija \(\alpha(n)\) je inverzna funkcija funkcije \(A(n, n)\) i ona jako sporo raste.↩︎