---
# System prepended metadata

title: Zajęcia 17.03.2021
tags: [xivlo]

---

###### 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:
```cpp=
pair< int, pair<int, int> > krawedzie[1003];
```

#### *\*)
Sortowanie zbioru krawędzi jest realizowane za pomocą funkcji `sort` z biblioteki `algorithm`:
```cpp=
sort(krawedzie, krawedzie+m);
```
> gdzie $m$ to liczba krawędzi

#### *\*\*)
Można to zrealizować za pomocą funkcji Find, lub w trakcie funkcji Union
```cpp=
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
```cpp=
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;
    ...
}

```