###### tags: `xivlo`

# Zajęcia 15.03.2021

## Union-Find 2

### Notatka
https://hackmd.io/@barnij/BJqoIKrmd

## Zadanie 'Rozbicie'
Zadanie polega na zapamiętaniu wszystkich krawędzi i krawędzi do usunięcia, a następnie obliczenie wyniku 'od tyłu', jednocześnie zapamiętując odpowiedzi.
Przypomnienie z omówienia:
- dla `n` rozłącznych zbiorów jest `n` spójnych składowych
- połączenie dwóch rozłącznych zbiorów jest równoznaczne ze zmniejszeniem liczby spójnych składowych o 1

> 'spójna składowa' to pewien spójny podgraf

## Zadanie 'Dysk twardy'
1. Zaznacz, że sektor $a$ jest zajęty
2. Połącz sektory $a$ i $a+1$
3. Jeśli reprezentant $a$ (po połączeniu z kroku 2.) jest zajęty, to wypisz "NIE", w przeciwnym przypadku wypisz numer tego reprezentanta (sektora).
## Tablica