4. Spravodajský Obecný Systém

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:

1. 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.

2. 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 alebo NIE.

Formát vstupu

Na prvom riadku vstupu sa nachádzajú čísla \(n\) a \(q\). Nasleduje \(q\) riadkov obsahujúcich informácie alebo otázky.

1. 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\)).

2. 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:

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