Sousedi ve stromu (38-Z1-4)

Začaly prázdniny, venku vedro jako na Sahaře a Kevin raději zůstává celé dny zavřený doma. Komu však toto extrémní klima svědčí, je Kevinův nový přírustek do jeho zahrádkářské kolekce - nově objevená bylina zvaná Chromatis Maxima. Tato pompézní rostlinka je speciální hlavně svými barevnými květy. Tu je modrý, tam je červený, onde zas tyrkysový. Kevin ani neumí všechny ty barvy pojmenovat.

Tuto květinu si Kevin nepořídil náhodou. Jakožto milovník čajových dýchánků si nenechal ujít informaci o tom, že odvar z jejích květů má hojivé účinky. Jaký tento účinek zrovna bude prý přesně odpovídá barvě květu, který k přípravě čaje použijeme.

Má to však jeden háček. Dle legend blahodárné účinky pramení z nedetekovatelných proudů energie, které květy jednotlivých barev vyzařují. Pokud nastane, že dva květy stejné barvy vyzařují příliš blízko u sebe, jejich frekvence se navzájem vyruší, celá rostlina se tím destabilizuje a ztrácí své léčivé vlastnosti. Pomůžete Kevinovy takové květy nalézt, aby je mohl včas zastřihnout?

Na vstupu dostanete zakořeněný uspořádaný strom. Každý vrchol obsahuje přirozené číslo B, které označuje barvu tohoto květu. Dále každý vrchol obsahuje uspořádaný seznam svých dětí, tedy vrcholů na vyšších vrstvách stromu.

Vaším úkolem je navrhnout algoritmus, kterým detekujete, zda existují dva vrcholy se stejným číslem B na stejné hladině stromu, nacházející se na této hladině bezprostředně vedle sebe. Pozor, že vrcholy počítáme jako vedlejší i pokud nesdílí stejného rodiče.

Na obrázku výše jako vedlejší počítáme dva červené vrcholy na předposlední vrstvě a žádné jiné.

Řešení

V této úloze hrají důležitou roli jednotlivé hladiny, na kterých se květy mohou nacházet. Hledané sousední květy totiž musejí růst vždy na stejné hladině. Ideálně bychom chtěli umět stromem projíždět postupně po hladinách od nejnižší po nejvyšší a v každé hladině projíždět květy zleva doprava dle jejich uspořádání na dané hladině. Když toto budeme umět, tak na každé hladině už v podstatě jen řešíme problém hledání dvou po sobě jdoucích totožných prvků v posloupnosti. A to už je znatelně lehčí úloha. Jak ale docílíme tohoto kýženého způsobu procházení stromem?

Využijeme prohledávání stromu do šířky (BFS), které započneme v jediném vrcholu na první hladině. Označme si ho $m$. BFS má totiž tu hezkou vlastnost, že prvky navštěvuje v pořadí odpovídajícímu vzdálenosti od $m$, která zas přesně odpovídá jednotlivým hladinám. Konkrétně tedy nejprve vložíme $m$ do fronty a následně v každém dalším kroku algoritmu vyjmeme první květ ze začátku fronty a označíme si ho $v$. Vzpomeňme si, že každý květ, a tedy i $v$, má dán uspořádaný seznam květů z něj vyrůstajících. Pro květ $v$ si tento seznam pojmenujeme $l_v$. Následně na konec fronty přidáváme všechny květy ze seznamu $l_v$ přesně v tom pořádí v jakém se v něm nacházejí.

Tímto způsobem budeme navštěvovat jednotlivé květy na každé hladině zleva doprava, jak jsme chtěli. Ještě však potřebujeme umět rozpoznat, na jaké se zrovna nacházíme hladině. Jinak by se nám mohlo stát, že prohlásíme za sousední poslední květ z nějaké hladiny s prvním květem z bezprostředně následující hladiny. Tomuto můžeme zamezit tak, že si na začátek fronty umístíme zvláštní symbol - zarážku. Vždy, když pak z fronty odebereme zarážku, tak si zvýšíme počítadlo hladiny a vložíme zarážku na konec fronty.

Časová složitost bude úměrná součtu počtu vrcholů (květů) a hran (spojnic mezi květy) stromu. Prostorová složitost bude stejná, jelikož si musíme pamatovat celý strom.