Struktura zbiorów rozłącznych ma 2 główne zastosowania:
-przepchanie zadania H
-oprócz tego: szybkie sprawdzanie czy dwa elementy są w tym samym zbiorze
Mamy do dyspozycji następujące operacje:
Union(x,y) - połączenie dwóch zbiorów w jeden.
Check(x,y) - sprawdzenie czy dwa elementy należą do tego samego zbioru.
Na początku każdy element należy do 1-elementowego zbioru.
Więc jeśli mamy n elementów, to także n zbiorów.
Połączenie będzie polegało na dołączeniu jednego zbioru do drugiego.
Lider zbioru to jest wierzchołek tego zbioru, który nie jest do nikogo podłączony.
W zbiorze istnieje jeden lider, pozostałe wierzchołki są do niego podłączone
(pośrednio, lub bezpośrednio).
Dla każdego wierzchołka będziemy pamiętać gdzie jest podłączony.
Oznaczmy przez p[x] wierzchołek, do którego x jest podłączony.
Załóżmy że jeżeli x jest liderem to p[x]=0.
Sprawdzenie, czy 2 elementy są w tym samym zbiorze to sprawdzenie czy mają takiego samego lidera.
Można tak, ponieważ każdy wierzchołek (a także każdy zbiór) ma jednoznacznie wyznaczonego lidera.
bool czy_naleza_do_tego_samego_zbioru(int x,int y)
{
return lider(x)==lider(y);
}
Jak sprawdzić lidera zbioru danego wierzchołka x?
sprawdzamy do kogo jest podczepiony x. to będzie p[x].
jeżeli p[x] nie jest liderem to sprawdzamy do kogo jest podczepiony p[x]. to będzie p[p[x]]
i tak dalej, aż znajdziemy lidera, czyli takie y(będące kilkukrotnym złożeniem p[x]), czli że p[y]=0.
Można to zrealizować przy pomocy rekurencji.
int lider(int x)
{
if(p[x]==0)return x;
return lider(p[x]);
}
Jak połączyć dwa zbiory A i B w jeden?
Trzeba podłaczyć jeden zbiór do drugiego, to znaczy do jednego z wierzchołków jednego zbioru należy podłaczyć lidera drugiego zbioru.
void Union(x,y)
{
p[x]=y;
}
W tej chwili mamy gotowy kod, jednak będzie on strasznie wolny.
Wykonam kilka optymalizacji:
Należy podłaczać mniejszy zbiór do większego.
Jeżeli podłączymy większy zbiór do mniejszego, to żeby sprawdzić lidera, jak i inne wierzchołki tego większego, należałoby przejść rekurencyjnie do wierzchołka, który został podłączony, a następnie przez ten mniejszy zbiór. Jeżeli podłączymy mniejszy do większego, to takich wierzchołków, które "mają taką długa drogę" będzie mniej.
Oznaczmy sobie dla lidera size(x) jako rozmiar zbioru, którego x jest liderem.
Jeżeli x przestaje być liderem to nas nie obchodzi co czym jest size(x). pozostaje teraz podczepić A do B, jeśli size(lider(x))<size(lider(y)) to podłączamy x do y. w przeciwnym przypadku y do x..
void Union(int x,int y)
{
int a=x,b=y;
if(size[Find(x)]>size[Find(y)]){a=y;b=x;}//zamiana tak, żeby a było elementem mniejszego zbioru
p[Find(a)]=Find(b);
size[b]+=size[a];
}
Kompresja ścieżki
Zwróćmy uwagę na fakt, że wierzchołek x i p[x] mają takiego samego lidera, o ile x nie jest liderem.
Jeżeli szukamy lidera x(jeśli nim nie jest, to znaczy że szukamy lidera p[x], a to znaczy że szukamy lidera p[p[x]](jeśli p[x] nie jest liderem) i tak dalej..
więc jak już znajdziemy, to możemy te pozostałe wierzchołki od razu podłączyć do lidera. Rekurencja pozwala sprytnie wykorzystać powyższą obserwację. Niewielkiej modyfikacji wymaga funkcja Find:
int Find(int x)
{
if(p[x]==0)return x;//to jest lider
p[x]=Find(p[x]);
return p[x];
}
Jeszcze na początku trzeba przygotować zmienne:
Dla każdego wierzchołka należy ustawić: Size[x]=1, p[x]=0.
przepraszam za zbyt sformalizowany styl, niejasność.
ale lepsze coś niż nic.. proszę o poprawę ewentualnych błedów.
