###### tags: `xivlo`

# Zajęcia 17.03.2021

## Minimalne drzewo rospinające (MST)
https://pl.wikipedia.org/wiki/Minimalne_drzewo_rozpinaj%C4%85ce

## Algorytm Kruskala do wyznaczania MST
Lista kroków:
1. Wczytaj zbiór krawędzi wraz z wagami *
2. Posortuj krawędzie rosnąco według wag **
3. Dla każdej krawędzi $(w,(a,b))$ ze zbioru posortowanych krawędzi:
a) Sprawdź, czy $a$ i $b$ są w jednym zbiorze połączonych wierzchołków ***
b) Jeśli a) prawdziwe to złącz zbiory do których należą $a$ i $b$

### Gwiazdki
#### *)
Zbiór krawędzi z wagami można trzymać w tablicy:

pair< int, pair<int, int> > krawedzie[1003];

#### *\*)
Sortowanie zbioru krawędzi jest realizowane za pomocą funkcji `sort` z biblioteki `algorithm`:

sort(krawedzie, krawedzie+m);

> gdzie $m$ to liczba krawędzi

#### *\*\*)
Można to zrealizować za pomocą funkcji Find, lub w trakcie funkcji Union

bool Union(int a, int b){
    int ra = Find(a);
    int rb = Find(b);
    if(ra==rb){
        return false;
    }
    ...
    return true;
}
...
if(Union(a,b)){
    //udalo sie
}else{
    //nie udalo sie
}

### Pary

pair<int,int> tab[10];
pair<int,int> a = make_pair(1,2);
pair< int, pair<int,int> > b = {3,{4,5}}; //make_pair(3,make_pair(4,5));

int c = a.first;
int d = a.second;

tab[0] = {9,10};
cout<<tab[0].first; //9

int e = b.second.first // 4
int f = b.second.second // 5
pair<int,int> g = b.second // {4,5}

pair< int,pair<int,int> > krawedzie[1003];

for(int i=0; i<m; i++){
    int a = krawedzie[i].second.first;
    int b = krawedzie[i].second.second;
    int w = krawedzie[i].first;
    ...
}