Zadanie
Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zaťiaľ programovať nevieš, ale chcel/a by si vedieť možeš skúsiť náš python tutoriál.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Kubovi na email [email protected]
Obyvatelia Alhirkuzu si už mnoho rokov museli poštu medzi sebou nosiť ručne (a nie práve stručne). To ich ale fakt nebaví. Neveríte? Veď si to skúste sami, celé dni prenášať správy medzi starými babkami, ktoré sa hádaju o tom, ktorá z nich má lepšiu panvicu. Preto dostali najmúdrejší inžinieri Alhirkuzu úlohu vymyslieť nový, lepší a rýchlejši systém prenosu správ. Po dvoch rokoch tvrdej práce (ktorú určite vykonali a určite iba doma nespali) sa rozhodli najať ľudí zo susednej obce, Kaespe aby do Alhirkuzu nainštalovali ich technológiu - sériové spojenie domácností. Z Kaespe teda poslali svojich inžinierov, ktorí do Alhikurzu nainštalovali sériové spojenie a naučili obyvateľov, ako s ním pracovať.
Správy sa prenášali bleskovou rýchlosťou a úplne samé, všetko fungovalo výborne… celých 5 dní. Vyzerá to tak, že z Kaespe neposlali dobrých inžinierov, ale iba nejakých lenivých. Kaespe sa už dôverovať nedalo, zostalo teda na inžinerov Alhikurzu sériové spojenia opraviť.
Babky (a aj iní obyvatelia) v Alhikurze sú ale nedočkavé a už počas opráv by chceli vedieť či si medzi sebou môžu znovu písať. Obec to ale sama nezvláda urobiť a preto sa obrátila na vás. Viete im pomôcť?
Študijný text
Túto úlohu si môžeme sformalizovať ako grafový problém. Na začiatku máme graf s \(n\) vrcholmi (domácnosťami), ktoré nie sú pospájané žiadnymi hranami (spojenia). Vždy keď inžinieri opravia nejaké spojenie medzi dvoma domácnosťami, zodpovedajúce dva vrcholy spojíme hranou. Pomedzi to sa obyvatelia pýtajú otázky, či existuje nejaká cesta (dokážu komunikovať) medzi vrcholmi \(x\) a \(y\) – teda či sú v tom istom komponente nášho grafu.
Efektívny algoritmus, ktorý rieši náš problém – spája vrcholy grafu hranami do spoločných komponentov a zodpovedá na otázky či sa nachádzajú dva vrcholy v spoločnom komponente – sa nazýva union-find.
V každom komponente budeme mať hierarchiu podobnú ako vo veľkej firme. Jeden zvolený vrchol bude “najvyšším šéfom” – reprezentantom celého komponentu. Niektoré ďalšie vrcholy budú jeho “priami podriadení”. A každý z nich môže mať zase veľa svojich podriadených, a tak ďalej.
Takúto hierarchiu si vieme až neuveriteľne ľahko uložiť v pamäti: pre každý vrchol v si stačí pamätať jediný ďalší vrchol: jeho bezprostredného šéfa. Výnimkou budú len reprezentanti komponentov, ktorí žiadneho šéfa nemajú. (Implementovať to môžeme napríklad tak, že si pre nich zapamätáme, že šéfujú sami sebe.)
Všimnite si, že hocikedy vieme veľmi ľahko určiť reprezentanta komponentu, v ktorom leží daný vrchol \(v\): stačí sa pozrieť na jeho šéfa, šéfa jeho šéfa, a tak ďalej, až sa po pár krokoch dostaneme do hľadaného vrcholu – “najvyššieho šéfa”. Ako zistiť, či vrcholy \(x\) a \(y\) ležia v tom istom komponente? Nájdeme vrcholy \(x′\) a \(y′\), ktoré sú reprezentantmi ich komponentov, a otestujeme, či \(x′ = y′\).
A ako spojiť komponenty obsahujúce vrcholy \(x\) a \(y\)? Opäť stačí, ak si nájdeme reprezentantov ich komponentov \(x′\) a \(y′\). Ak platí \(x′ = y′\), nič netreba robiť, vrcholy sú už v tom istom komponente. Inak sú vrcholy \(x\) a \(y\) v rôznych komponentoch. Preto nastavíme, že odteraz je vrchol \(y′\) šéfom vrcholu \(x′\) – a teda reprezentantom pre všetky vrcholy oboch bývalých komponentov. Všimnime si, že takto nevytvoríme cyklus medzi šéfmi a z každého vrcholu tohto spojeného komponentu sa postupným pýtaním na šéfov dostaneme až k \(y′\). Na začiatku výpočtu máme \(n\) izolovaných vrcholov. Teda každý vrchol tvorí jeden komponent a je teda aj reprezentantom dotyčného komponentu.
Takéto riešenie by mohlo byť v praxi často rýchle, avšak pri najhoršom možnom vstupe je ešte stále dosť pomalé. Všimnime si, že keď si zakreslíme všetky hrany z \(v\) do šéfa \(šéf [v]\) ako graf, každý komponent bude zodpovedať jednému orientovanému stromu, v ktorého koreni je jeho reprezentant. Čím sú tieto stromy hlbšie, tým sú operácie s nimi pomalšie. Preto použijeme dve vylepšenia, ktoré nám umožnia zmenšiť hĺbku týchto stromov a teda aj znížiť počet dotazov na šéfov:
Prvým zlepšením je kompresia cesty v strome. Predstavme si, že hľadáme reprezentanta pre vrchol \(a\). Zistíme, že šéfom \(a\) je \(b\),šéfom \(b\) je \(c\) a šéfom \(c\) je hľadaný reprezentant \(d\). V tomto okamihu ale môžeme zmeniť vrcholom \(a\) aj \(b\) šéfa priamo na vrchol \(d\), a teda už nikdy viac nebudeme musieť prechádzať po ceste \(abcd\), ktorú sme práve rozbili.
Druhé zlepšenie pomáha udržiavať naše stromy košaté ale nie veľmi hlboké. Pre každý komponent si budeme pamätať jeho rád, ktorý bude na začiatku \(0\). Keď ideme spájať dva komponenty s reprezentantmi \(x′\) a \(y′\), tak sa pozrieme na rády týchto komponentov. Ak má jeden z nich menší rád ako druhý, tak reprezentant toho komponentu s väčším rádom bude šéfom reprezentanta komponentu s menším. V opačnom prípade bude \(y′\) šéfom \(x′\), pričom novovzniknutému komponentu zvýšime rád o \(1\).
Dá sa dokázať, že pre takto vylepšený algoritmus platí nasledovný odhad časovej zložitosti: ľubovoľnú postupnosť \(m\) operácií vykoná v čase \(O(m \cdot \alpha(n))\). Funkcia \(\alpha(n)\) je tzv. inverzná Ackermannova funkcia. Táto funkcia rastie až nepredstaviteľne pomaly: Pre ľubovoľné rozumne veľké \(n\) je \(\alpha(n) \leq 5\), takže náš algoritmus prakticky potrebuje v priemere na každú požiadavku len konštantne veľa operácií.
Úloha
V obci je \(n\) domácností, označených od \(0\) po \(n-1\), ktoré chcú medzi sebou komunikovať sériovým spojením. Na začiatku sú všetky spojenia pokazené (nedá sa cez ne komunikovať). Prichádzajú nám informácie a otázky:
Inžineri opravili spojenie medzi dvoma domácnosťami, čo znamená, že medzi týmito domacnosťami sa odteraz dokážu prenášať správy. Inžinieri ale nie sú dokonalí, takže informáciu o tom, že spojenie medzi dvoma domácnosťami je opravené, môžu občas poslať aj vtedy, keď spojenie bolo opravené už predtým.
Obyvatelia dvoch domácností chcú vedieť, či medzi sebou dokážu komunikovať. Takáto kuminkácia nemusí viesť priamo, takže správa môže prejsť aj cez iné domácnosti. Vašou úlohou je na takúto otázku odpovedať
ANO
aleboNIE
.
Formát vstupu
Na prvom riadku vstupu sa nachádzajú čísla \(n\) a \(q\). Nasleduje \(q\) riadkov obsahujúcich informácie alebo otázky.
Informácia hovoriaca o oprave spojenia medzi dvoma domácnosťami je v tvare
spojenie x y
, kde \(x\) a \(y\) sú čísla domácností medzi ktorými sa spojenie opravilo (platí \(0 \leq x,y \leq n-1 \wedge x \neq y\)).Otázka obyvateľov, či medzi sebou dokážu komunikovať je v tvare
dalobysa x y
, kde \(x\) a \(y\) sú čísla domácností, ktoré chcú vedieť či medzi sebou dokážu komunikovať (platí \(0 \leq x,y \leq n-1 \wedge x \neq y\)).
Formát výstupu
Pre každú otázku obyvateľov vypíšte ANO
alebo
NIE
podľa toho, či sa medzi týmito domácnosťami dá
komunikovať.
Hodnotenie
Je 5 sád vstupov v ktorých platia nasledovné obmedzenia:
Sada | 1. | 2. | 3. | 4. | 5. |
---|---|---|---|---|---|
\(1 \leq n \leq\) | \(1000\) | \(10000\) | \(500000\) | \(500000\) | \(1000000\) |
\(1 \leq q \leq\) | \(1000\) | \(5000\) | \(80000\) | \(80000\) | \(80000\) |
Príklad
Input:
4 7
spojenie 0 1
dalobysa 0 3
spojenie 1 2
dalobysa 0 3
spojenie 2 3
dalobysa 0 3
dalobysa 1 3
Output:
NIE
NIE
ANO
ANO
Input:
7 10
dalobysa 2 1
spojenie 2 3
spojenie 2 5
dalobysa 1 0
dalobysa 5 0
spojenie 0 3
spojenie 3 4
spojenie 2 1
spojenie 1 2
dalobysa 0 1
Output:
NIE
NIE
NIE
ANO
V zadaní tejto úlohy ste dostali študijný text o dátovej štruktúre union-find. Ak union-find nepoznáte, odporúčame vám prečítať si ho pred čítaním tohto vzoráku.
Zrekapitulujme si, čo vieme o union-finde a o tejto úlohe. Union-find nám umožňuje v grafe robiť dve operácie: spájať vrcholy do toho istého komponentu, a zisťovať, či sú dva vrcholy v tom istom komponente grafu.
Pozrime sa teraz na to, s čím v tejto úlohe začíname: - Máme obec v ktorej sú domy → tie budú vrcholmi grafu - Medzi nimi na začiatku nie sú žiadne funkčné spojenia → nemáme žiadne hrany - Z tohto nám aj vyplýva, že každý dom začína ako samostantný komponent grafu (graf neobsahuje žiadne hrany)
Postupne sa budú spojenia medzi domami opravovať. V grafe to budeme reprezentovať tak, že medzi domami resp. vrcholmi, ktoré reprezentujú domy v grafe, pridáme hranu. Tým sa nám budú postupne vrcholy spájať do komponentov.
Okrem toho budeme potrebovať aj zistiť, či medzi dvomi domami existuje funkčné spojenie (ktoré môže viesť aj cez viacero iných domov).
Čo si môžeme všimnúť je, že operácie, ktoré používame v tejto úlohe sú rovnaké ako tie, ktoré používa union-find.
Implementácia
Teraz sa pozrime na to, ako sa dá union-find implementovať a ako sa dá použiť na riešenie tejto úlohy.
Začneme s implementáciou v Pythone. Potom sa pozrieme aj na to, ako by finálny program mohol vyzerať v C++.
Ako prvý krok si pripravíme polia na ukladanie rodičov a rádov vrcholov.
= [i for i in range(n)]
rodic = [0 for i in range(n)] rad
Premenná \(n\) označuje celkový počet domov v obci, teda aj počet vrcholov grafu.
Teraz si napíšeme funkciu, ktorá nám vráti rodiča vrchola \(v\).
Funkcia bude rekurzívna, keďže potenciálne budeme potrebovať rekurzívne
zisťovať rodiča rodiča vrchola \(v\),
atď.
def najdi_reprezentanta(v):
if v == rodic[v]:
# v je rodičom seba samého => v je reprezentantom komponentu
return v
else:
# v nie je reprezentantom komponentu => nájdeme reprezentanta
= najdi_reprezentanta(rodic[v]) # nájdeme reprezentanta
reprezentant = reprezentant # aplikujeme kompresiu cesty
rodic[v] return reprezentant
Ďalšia vec, ktorú potrebujeme implementovať, je funkcia, ktorá nám spojí dva vrcholy \(x\) a \(y\) do jedného komponentu.
def spoj(x, v):
= najdi_reprezentanta(x)
x = najdi_reprezentanta(y)
y # namiesto x a y použijeme reprezentantov ich komponentov
if x == y:
# x a y sú už v jednom komponente
return
if rad[x] < rad[y]:
# rád x je menší ako rád y => spojíme x pod y
= y
rodic[x] elif rad[x] > rad[y]:
# rád x je väčší ako rád y => spojíme y pod x
= x
rodic[y] else:
# rády sú rovnaké => spojíme y pod x a zvýšime rád x
= x
rodic[y] += 1 rad[x]
Obe funkcie union-findu sme už implementovali. Zostáva nám implementovať načítavanie vstupu, použitie union-findu a výpis výsledku.
Na začiatok načítame zo vstupu počet domov \(n\) a počet informácii (resp. otázok) \(q\).
= input().split()
n, q = int(n), int(q) n, q
Teraz budeme postupne načítavať \(q\) informácií a odpovedať na otázky.
for i in range(q):
= input().split()
typ, x, y = int(x), int(y) # prevedieme x a y na čísla
x, y
if typ == "spojenie":
# spojenie medzi domami x a y bolo opravené => spojíme vrcholy x a y
spoj(x, y)else:
# chceme zistiť, či medzi domami x a y existuje funkčné spojenie
if najdi_reprezentanta(x) == najdi_reprezentanta(y):
# vrcholy x a y sú v jednom komponente => existuje funkčné spojenie
print("ANO")
else:
# vrcholy x a y nie sú v jednom komponente => neexistuje funkčné spojenie
print("NIE")
Ukázali sme si postupne všetky časti programu. Teraz si ukážeme, ako by mohol vyzerať celý program.
= input().split()
n, q = int(n), int(q)
n, q
= [i for i in range(n)]
rodic = [0 for i in range(n)]
rad
def najdi_reprezentanta(v):
if v == rodic[v]:
return v
else:
= najdi_reprezentanta(rodic[v])
reprezentant = reprezentant
rodic[v] return reprezentant
def spoj(x, v):
= najdi_reprezentanta(x)
x = najdi_reprezentanta(y)
y
if x == y:
return
if rad[x] < rad[y]:
= y
rodic[x] elif rad[x] > rad[y]:
= x
rodic[y] else:
= x
rodic[y] += 1
rad[x]
for i in range(q):
= input().split()
typ, x, y = int(x), int(y)
x, y
if typ == "spojenie":
spoj(x, y)else:
if najdi_reprezentanta(x) == najdi_reprezentanta(y):
print("ANO")
else:
print("NIE")
Implementácia v C++
Postup implementácie v C++ je v podstate rovnaký ako v Pythone.
Hlavný rozdiel je v syntaxi. Polia a funkcie sa definujú inak ale všetky
princípy sú rovnaké.
Keďže postup je rovnaký, nebudeme ho opakovať a pozrieme sa iba na to, ako by mohol vyzerať celý program.
#include <iostream>
using namespace std;
int n, q;
int* rodic;
int* rad;
int najdi_reprezentanta(int v) {
if (v == rodic[v]) {
return v;
} else {
int reprezentant = najdi_reprezentanta(rodic[v]);
[v] = reprezentant;
rodicreturn reprezentant;
}
}
void spoj(int x, int y) {
= najdi_reprezentanta(x);
x = najdi_reprezentanta(y);
y
if (x == y) {
return;
}
if (rad[x] < rad[y]) {
[x] = y;
rodic} else if (rad[x] > rad[y]) {
[y] = x;
rodic} else {
[y] = x;
rodic[x] += 1;
rad}
}
int main() {
>> n >> q;
cin
= new int[n];
rodic = new int[n];
rad
for (int i = 0; i < n; i++) {
[i] = i;
rodic[i] = 0;
rad}
for (int i = 0; i < q; i++) {
;
string typint x, y;
>> typ >> x >> y;
cin
if (typ == "spojenie") {
(x, y);
spoj} else {
if (najdi_reprezentanta(x) == najdi_reprezentanta(y)) {
<< "ANO" << endl;
cout } else {
<< "NIE" << endl;
cout }
}
}
}
Časová a pamäťová zložitosť
Časová zložitosť tohto riešenia je zhodná s časovou zložitosťou
union-findu. Všetko, čo vykonávame okrem union-findu trvá čas \(O(1)\) (konštantný čas).
Takže celková časová zložitosť je \(O(q \cdot
\alpha(n))\).
Dokopy vykonáme \(q\) operácií a
pracujeme na grafe s \(n\)
vrcholmi.
\(\alpha(n)\) je inverzná funkcia
Ackermannovej funkcie. Rastie veľmi pomaly a jej hodnota je efektívne
vždy menšia ako \(5\).
Pamäťová zložitosť je \(O(n)\), pretože potrebujeme \(n\) prvkov na uloženie rodičov a \(n\) prvkov na uloženie rádov komponentov.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.