###### tags: `xivlo`

# Zajęcia 10.03.2021

## Notatka
Chcemy utrzymywać strukturę zbiorów rozłącznych, tj. mamy $n$ liczb (od $1$ do $n$):

- $find(x)$ → identyfikator zbioru w którym jest $x$
- $union(x,y)$ → złącz zbiory w których są $x$ i $y$
- $makeSet(n)$ → stwórz strukturę, gdzie każdy element jest w osobnym (jednoelementowym) zbiorze

> $find(x)$ == $find(y)$ sprawdza czy $x$ i $y$ są w tym samym zbiorze

### Identyfikatory zbiorów
Każdy zbiór będzie posiadał jeden wyróżniony element, który pozwoli nam identyfikować ten zbiór - będziemy go nazywać __reprezentantem zbioru__.

Jeśli elementy zbioru to liczby od $1$ do $n$, to reprezentantów możemy zapisać w tablicy `repr[]`, gdzie dla elementu $x$ zajrzymy w miejsce `repr[x]` i na podstawie tej informacji, podejmiemy dalszą analizę (tj. zajrzymy w `repr[repr[x]]`) lub zwrócimy wynik. Reprezentantem jest element $y$, dla którego zachodzi `repr[y]==y`.

### Implementacja makeSet
Przykład dla zbioru wielkości 10.

int repr[11];

void makeSet(int n){
    for(int i=1; i<=10; i++){
        repr[i]=i;
    }
}

> Na początku każdy jest swoim reprezentantem.

### Implementacja Find (gorzej)

int Find(int x){
    if(repr[x]==x)
        return x;
    return Find(repr[x]);
}

### Implementacja Union (gorzej)

void Union(int x, int y){
    int rx = Find(x);
    int ry = Find(y);
    
    repr[rx] = ry;
}

### Find (lepiej) - optymalizacja ścieżek
Pierwsza implementacja, może doprowadzić do sytuacji, że utworzone długie zależności w tablicy reprezentantów, będą wymagały liniowego czasu przy każdym wywołaniu funkcji Find. To bardzo niedobrze. Możemy to naprawić, wymagając, by funkcja Find wracając z wynikiem (numerem reprezentanta zbioru) aktualizowała/*przepinała* elementy wprost pod reprezentanta.

Przykład:

Wywołujemy naprawiony `Find(x)` na powyższym zbiorze i otrzymujemy naprawioną tablicę `repr`, gdzie elementy $X,D,C,B$ i $A$ mają teraz na swoich pozycjach w tablicy `repr` wartość $Z$:

#### Implementacja

int Find(int x){
    if(repr[x]==x)
        return x;
    repr[x] = Find(repr[x])
    return repr[x];
}

### Union (lepiej) - rangi
Nasz ulepszony Find 'przepina' elementy zbioru bezpośrednio do reprezentanta zbioru. Mając do wyboru połączenie dwóch zbiorów, chcemy połączyć mniejszy do większego, a nie na odwrót - w ten sposób będziemy mieli mniej do 'przepinania'. By wiedzieć, który zbiór jest większy, dodamy do naszego programu tablicę Rank, utrzymującą wielkości zbiorów, których reprezentantami są dane elementy.

> Po wykonaniu funkcji makeSet, Rank każdego elementu jest równy zero. Gdy łączymy dwa zbiory o równych 'rangach', reprezentantowi złączonych zbiorów zwiększami rangę.

#### Implementacja

#include <algorithm> //do funkcji max
// mamy tablicę rank, posiadającą informację o 'wielkości' zbioru
//...

void Union(int x, int y){ 
    int rx = Find(x);
    int ry = Find(y);
    
    //jeśli zbiory połączone to kończymy
    if (rx == ry)
        return;
    
    if(Rank[rx] < Rank[ry]){
        repr[rx] = ry;
    }
    else{ 
        repr[ry] = rx;
        //można tak
        Rank[rx] = max(Rank[rx], Rank[ry]+1);
        // lub tak
        // if(Rank[rx] == Rank[ry])
        //     Rank[rx]++;
    }
}