Zadanie

Krízový štáb KSP musí zasadnúť, no vzhľadom na aktuálnu epidémiu, nikto nikomu neverí. Nikto predsa nechce nikoho nakaziť a ani nece byť nakazený. Teda nie zase každý každému. Niektorí niekomu predsa len veria. Napríklad takému Krtkovi nikto neverí, lebo stále niekam behá, chodí na všetky stretká a stretáva veľa ludí. Naopak Samovi verí takmer každý, lebo všetci vedia, že celý deň sedí za počítačom a niečo kódi. Aby bola na zasadnutí krízového štábu dobrá atmosféra, chceme, aby mal každý ľudí, ktorím verí hneď vedľa seba.

Úloha

Krízový štáb má \(n\) členov a zasadá za okrúhlym stolom. Títo členovia majú dokopy \(m\) požiadaviek tvaru \(x y\) čo znamená, že člen číslo \(x\) verí členovi číslo \(y\). Dokážeme usadiť všetkých členov tak, aby každý člen mal všetkých ľudí, ktorím verí priamo vedľa seba?1

Formát vstupu

Na prvom riadku sa nachádzajú dve čísla \(n\) a \(m\), (\(1\leq n,m \leq 100\,000\)) počet členov krízového štábu a počet ich požiadavok. Nasleduje \(m\) riadkov tvaru \(x_i y_i\), (\(0\leq x_i,y_i<n, x_i \not = y_i\)) ktoré hovoria, že člen číslo \(x_i\) verí členovi číslo \(y_i\).

Formát výstupu

Vypíšte jeden riadok so slovom ano, ak sa dá usadiť všetkých členov tak, aby bola na zasadnutí dobrá atmosféra alebo nie, ak sa to nedá.

Príklady

Input:

2 1
0 1

Output:

ano

Krizový štáb má dvoch členov a jeden z nich verí tomu druhému, takže keď ich posadíme vedľa seba, všetky podmienky budú splnené.

Input:

4 3
0 1
0 2
0 3

Output:

nie

Člen číslo 0 verí trom ďalším členom, ale priamo vedľa seba môže mať len dvoch ľudí, takže nevieme splniť všetky jeho požiadavky zároveň.

Input:

5 3
0 2
0 1
3 0

Output:

nie

Ak má vedľa 0 sedieť 1 aj 2, už nemôže sedieť 3 vedľa 0.

  1. Ak napríklad niekto nikomu neverí, je vlastne jedno kto pri ňom sedí.↩︎

Prvá vec, ktorú si treba uvedomiť je, že ak \(x\) chce sedieť vedla \(y\), tak to znamená, že vedľa seba musia sedieť. Rovnako ako keď chce sedieť \(y\) vedľa \(x\). Na poradí v tejto dvojici teda nezáleží a treba si dať pozor, ak sú na vstupe obe poradia. Ďalšie jednoduché pozorovanie je, že každý sa môže nachádzať najviac v dvoch rôznych požiadavkach. Sedieť vedla neho predsa môžu len dvaja ľudia. Ak to tak nie je, vieme, že požiadavky nesplníme. Ak je však splnená táto podmienka, môžu nastať nasledovné dva prípady. Buď požiadavky na seba nadvezujú a skončia na človeku, ktorý sa nachádza len v jednej požiadavke, teda napríklad:

0 1
1 2
2 3

Alebo na seba nadvezujú a tvoria cyklus:

4 5
5 6
6 7
7 4

Úsekov oboch typov môže byť viac. Ak nájdeme viac úsekov prvého typu, tak nám to nevadí. Problém nastáva pri druhom type. Nezáleží na tom či by boli cykly prepojené alebo nie, nikdy by sme nevedeli splniť všetky podmienky (buď by mal jeden človek sedieť vedľa viac ako 2 ľudí alebo by museli sedieť za 2 stolmi). Teda až na jeden špeciálny prípad, kedy sú v tomto cykle úplne všetci a vtedy vypisujeme ano.

Ako na to

Prvý krok je, správne si uložiť vstup. Klasická dátová štruktúra pri podobných úlohách sa volá zoznam susedov. Budeme mať teda dvojrozmerné pole (zoznam zoznamov, vektor vektorov či rovno zoznam setov), nazveme ho susedia. V tomto poli bude na indexe \(i\) zoznam všetkých, ktorí chcú alebo, s ktorými chce sedieť človek \(i\).

Následne budeme hľadať, či je tam nejaký cyklus. To síce nie je nič ťažké, ale pár desiatok riadkov to zaberie. Zvolíme si jedného človeka (to znamená postupne každého :P) a zapamätáme si, že pri ňom začíname. Vieme, že má jedného alebo dvoch susedov. Jedného si zvolíme (neskôr aj druhého) a ideme si označovať cestu, ktorou nás bude viesť (každého navšíveného suseda si označíme ako videného). Každý ďalší človek ku ktorému prídeme, bude mať ako suseda toho, od ktorého sme vyšli a ešte jedného (alebo žiadneho) suseda. Ak žiadneho, tak cesta skončila a je to OK, lebo cyklus sme nenašli. Ak ešte má suseda, tak pokračujeme. Keď budeme takto pokračovať a stane sa, že narazíme na človeka, s ktorým sme začínali, vieme, že je to cyklus.

Časová a pamäťová zložitosť

Máme \(n\) ľudí a \(m\) požiadaviek. Víme však, že každý môže mať najviac dve požiadavky, takže môžeme povedať že \(m\) je rádovo to čo \(n\). Náš program teda vyzerá tak, že začíname postupne u každého človeka (to je zatiaľ \(O(n)\)) a ideme označovať “cestu” jeho susedov. Tu by sa mohlo zdať, že to môže byť zase \(n\) krokov, ale treba si uvedomiť, že samotné označenie človeka stačí robiť každému iba raz. Teda ak by sme mali označovať cestu, a narazíme pri tom na niekoho už označeného, tak s tým rovno aj prestaneme, lebo sme to predsa už spravili. Teda ak náš prvý cyklus narazí na niekoho označeného, vlastne nič nerobí. Teda je to stále iba \(O(n)\).

Pamätáme si zase len niekoľko polí veľkost \(n\), teda aj pamäťová zložitosť je \(O(n)\)

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