Mačička a jej partia veľmi radi chodia do cukrárne. Keďže je ale partia veľmi veľká, tak sa tam nebaví každý s každým. Členovia, ktorý sa spolu bavia tvoria dvojice, ktoré voláme kamarátstva. Kamaráti sa spolu potom stretávajú pri koláčiku. V Kocúrkove sú presne dve cukrárne - jedna podáva iba ríbezľové koláče a druhá iba banánové koláče. Každý kamarát má samozrejme svoju preferenciu a je šťastný, iba ak idú do cukrárne, ktorá predáva jeho obľúbený koláč. V Kocúrkove sú všetci veľmi tvrdohlavý a nemajú radi zmenu. Preto každé kamarátstvo chodí, a aj vždy chodiť bude do tej istej cukrárne. Chodia tam dokonca aj vtedy, keď obaja kamaráti preferujú druhú príchuť koláčiku.
Kocúrkovo sa nevyhlo inflácií a chodiť na predražené koláčiky je v dnešnej dobe veľmi neekonomické. Mačička chce, aby jej partií ostali nejaké peniaze aj na spoločné výlety (napríklad na Mars, aj keď nevedia, čo stojí lístok) a povedala si, že takto to ďalej nepôjde. Dobre vie, že na to aby jej partia s $n$ členmi zostala pokope je potrebných iba $n-1$ kamarátstiev (partia je pokope, ak sa ľubovoľní dvaja členovia vedia skontaktovať buď priamo, alebo cez nejakých svojich kamarátov. Ako všetci dobre vieme, nemôžete napísať človeku, s ktorým nie ste kamarát). Mačičke nerobí problém pomôcť niektorým kamarátstvam aby sa rozpadli, ale chce, aby jej partia zostala pokope a všetci boli štastní. To znamená, že každému kamarátovi musí ostať aspoň jedno kamarátsvto, ktoré chodí do jeho obľúbenej cukrárne.
Máme partiu o $n$ členoch ktorá je pokope a $m$ kamarátstiev. Každý člen má rád buď ríbezľové alebo banánové koláčiky. Každé kamarátstvo má dané, do ktorej z dvoch cukrární chodí. Pomôžte Mačičke nájsť $n-1$ kamarátstiev, ktoré keď ostanú tak bude platiť, že skupina je pokope a každý člen má aspoň jedno kamarátstvo, ktoré chodí do jeho obľúbenej cukrárne alebo jej povedzte že sa to nedá.
V prvom riadku vstupu sú čísla $n$ a $m$ udávajúce veľkosť partie a počet kamarátstiev. Nasleduje $m$ riadkov. Na $i$-tom riadku sú medzerou oddelené čísla $a$, $b$ ($1 \leq a, b \leq n$) určujúce indexy členov partie ktorý sa kamarátia a znak $s$ ($s$ ∈ {R, B}), ktorý určuje, do ktorej cukrárne chodia na koláčiky. Na poslednom riadku je string $n$ znakov $p$, $p_j$ ∈ {R, B}, kde $p_j$ je preferencia kamaráta $j$.
| Sada | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $2 \leq n \leq$ | $20$ | $100$ | $10^5$ | $3*10^5$ |
| $1 \leq m \leq$ | $1\,000$ | $10^4$ | $10^5$ | $3*10^5$ |
Je zaručené, že v prvej a tretej sade kamarátstva nevytvárajú cyklus (teda pre ľobovolných dvoch členov partie platí, že ak sa chcú prostrednictvom kamarátstiev skontaktovať, tak existuje práve jedna možnosť ako to vedia docieliť).
Ak riešenie neexistuje, vypíš jeden riadok, na ktorom bude napísané
Neda sa. Ak riešenie existuje vypíš medzerou oddelené $i$ určujúce indexy kamarátstiev, ktoré
ostali.
Input:
`3 3
1 2 R
1 3 B
2 3 B
RRB`
Output:
`3 1`
Necháme tretie a prvé kamarátstvo. Správne riešenie by tiež bolo nechať druhé a prvé kamarátstvo.
Input:
`3 4
1 2 R
1 2 B
1 3 B
2 3 B
RRR`
Output:
`Neda sa`
Žiadne kamarátstvo 3 člena nechodí do cukrárne, kde predávajú ríbezľové koláčiky.
Graf ktorý vznikne z povôdného ponechaním iba n-1 hrán a zároveň zostane súvislý sa volá kostra. Preferencie kamarátov (teda banánový alebo ríbezlový koláč) budeme volať farba - takže budeme sa rozprávať o farbení hrán a vrcholov.
Začneme so sadami 1 a 3. Tieto sady su velmi ľahké ako na myšlienku tak aj na implementáciu, kedže graf, ktorý dostaneme na vstupe je už rovno kostra. Vôbec sa teda nemusíme zaujímať o to, ktoré hrany použijeme (kedže graf ktorý dostaneme už ich má n-1) a len chceme zistiť, či sú všetky vrcholy nášho grafu šťastné.
Pre každý vrchol prejdem všetky jeho hrany a ak nemá hranu svojej farby tak neexistuje riešenie a rovno to môžem vypísať. Inak program dobehne a ja na konci vypíšem riešenie - vypíšem hrany zo vstupu. Časová zložitosť tohto programu je O(n + m), keďže si musím načítať aj vstup. Pamäťová je taktiež O(n + m).
Teraz už vieme skontrolovať, či kostra robí graf šťastným. Čo môžeme spraviť ďalej je vygenerovať všetky možné kostry grafu a pre každú z nich skontrolovať, či daná kostra spĺňa podmienky zo zadania. Postupne generovať kostry sa dá viacerými spôsobmi napr. za pomoci bitmasiek ale jednoduchšie je možno použiť rekurzívne DFS. Bude to pomalé a výrazne náročnejšie na implementáciu ako vzorové riešenie. Ak máme napríklad $10^5$ hrán, 1001 vrcholov a chceme vybrať všetky kombinácie 1000 hrán tak to bude $\binom{10^5}{1000}$ a to vám kalkulačka odmietne vypočítať nakoľko je to príliš veľa. Odhad zložitosti bude približne $m!$ (m je počet hrán) a to by neprešlo ani na prvej sade veľmi pravdepodobne.
Zamyslime sa teraz nad tým, že väčšina kostier, ktoré by sme vygenerovali bruteforce riešením by nespĺňali podmienku, že všetky vrcholy sú šťastné, hlavne teda ak by kostra, ktorej vrcholy sú všetky šťastné neexistovala a my by sme museli generovať všetky možnosti. Namiesto toho, aby sme vytvorili kostru a potom kontrolovali, či sú vrcholy šťastné cheme kontrolovať či sú šťastné už keď ju vytvárame.
Hrany budeme pridávať vo viacerých fázach. Stav kostry si budeme pamätať ako union-find. Pre každý vrchol si chceme pamätať, či sa nachádza v komponente a aký vrchol je v jeho komponente koreňom. Začneme tým, že prejdeme všetky hrany a pokiaľ majú oba vrcholy a aj hrana rovnakú farbu a zároveň sa ešte nenachádzajú v rovnakom komponente tak ich pridáme do kostry a upravíme rodičov ich komponentu. Teraz spustíme z rodičov komponentu BFS a budeme prechádzať cez jednotlivý komponent a pridávať také hrany ktoré spĺňajú podmienku že ešte nie sú v danom komponente a vedú do vrcholu ktorý má ich farbu, tiež samozrejme upravíme komponenty.
Po tejto fáze by mali byť všetky vrcholy spokojné. Pokiaľ nie sú tak kostra neexistuje. Prepokladajme sporom, že existuje riešenie ale náš algoritmus ho nenašiel. Postupovali sme spôsobom opísaným vyžšie a kedže riešenie existuje tak existuje aj hrana ktorú sme nepoužili ale je súčasťou riešenia. Tá hrana musí buď spájať vrcholy s ktorými oboma zdieľa farbu alebo spájať vrchol rovnakej farby s vrchol druhej farby ktorý je už šťastný (ak nerobí žiaden vrchol štastný tak zjavne nezmení to či to riešenie existuje alebo nie takže nás nezaujíma). To je ale v spore s prepokladom, že sme použili vyžšie opísaný algoritmus. Pokiaľ by robila oba vrcholy s ktorými je spojená šťastné tak by bola pridaná už pri prvotnom prechádzaní hrán. Ak robí iba jeden vrchol šťastný tak by bola pridaná v druhej fáze, keď pripájame nové vrcholy cez BFS (všimnime si, že ak robí jeden vrchol šťastným ale druhý ostane neštastný tak tiež nie je relevantná pre riešenie lebo po jej pridaní ostane vrchol smutný).
Treba si teraz ešte uvedomiť to, že sme uspokojili všetky vrcholy neznamená, že máme kompletné riešenie ale iba vieme že existuje, mohli nám totiž ostať viaceré nespojené komponenty. To vyriešime tak, že prejdeme všetky hrany a už sa nezaujímame o to akú majú farbu a pridáme všetky také, ktoré nám spoja dva rôzne komponenty. Keďže graf na vstupe je súvislý tak určite existujú hrany, ktorými vieme aj našu kostru spraviť súvislú.
Ak ste nikdy nepočuli o union find tak odporúčam pozrieť materiály na ksp school (https://school.ksp.sk/courses/data-structures-2/union-find/union-find-intro/), skrátená verzia je taká že si pamätáme koreň komponentu a tiež hlbkú stromu keď si ho v tom vrchole zakoreníme. Keď spájame dva komponenty tak ako rodiča komponentu s nižšou hĺbkou nastavíme koreň väčšieho komponentu. Keď chceme zistiť v akom komponente je vrchol tak sa rekurzívne budeme volať na rodiča každého vrcholu až kým neprídeme k vrcholo ktorý je rodič samého seba a to bude hladaný koreň, pokial majú dva vrcholy rovnaký koreň komponentu tak sú v rovnakom komponente.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete