# ADS B - Holubi

Rozesílání holubů funguje jako průchod grafem do šířky:

$1.$ Zvolím chovatele $a$ a pošlu všechny holuby. Adresáti také pošlou další holuby. BÚNO mě nazjímají holubi, kteří posílají zprávu již tomu, kdo ji dostal.
$2.$ Tím zjistím, komu může $a$ přímo i nepřímo zprávu doručit. Pokud však je někdo, kdo nebyl obeslán, pak tento chovatel $b$ musí být schopen nějakým způsobem doručit zprávu $a$. Žádní jiní chovatelé dostupní z $a$ mě nezajímají, jelikož těm může odeslat zprávu $a$
$3a.$ Jestliže ani tohoto není schopen, pak hledám dalšího chovatele $c$, který nemůže být obeslán, a tento musí zaslat zprávu jak $a$, tak $b$, atd.
$3b.$ Pokud $b$ může doručit zprávu $a$, tak chovateli $c$ stačí, aby byl schopen doručit zprávu $b$.

Grafově:

$0.$ Všechny vrcholy jsou na začátku neprozkoumané. Každý holub představuje výstupní hranu z vrcholu.
$1.$ Vyberu náhodně jeden (neprozkoumaný) vrchol, označím jej jako volný vrchol.
$2.$ Všechny vrcholy dosažitelné z volného vrcholu (pomocí BFS) označím jako prozkoumané. Do prozkoumaného vrcholu se již nevracím. Volný vrchol přepíšu na prozkoumaný jen v případě, je-li jiný než startovní vrchol.
$3.$ Je-li ještě neprozkoumaný vrchol, $\to 1.$
$4.$ Zkontroluji počet volných vrcholů. Je-li jeden, pak existuje alespoň jedno řešení. Je-li jich více, pak řešení neexistuje.


Postup:

$1.$ Z 1 prozkoumám 356, z 6 otevřu 1, ale nepřepíšu (jelikož je to tentýž BFS), 1. je volný
$2.$ Z 2 prozkoumám 56, nic nedělám, 2. je volný
$3.$ Z 4 prozkoumám 13, 1 přepíšu na prozkoumaný, 4. je volný.
$4.$ Tento graf nemá řešení. Nejlepší výchozí vrchol by byl 4, pak ale by 2 nedostal zprávu.

Správnost:

Je-li ne-poslední volný vrchol dosažitelný z nějakého jiného vrcholu v rámci odlišného BFS (tzn. nenastane cyklus), pak jej mohu označit jako prozkoumaný. Tím pádem jsem zároveň schopen prozkoumat všechny vrcholy, které jsem prozkoumal z tohoto přepsaného vrcholu.

Ačkoli startovní vrchol může být pouze jeden, není to jediné možné řešení; výchozími vrcholy mohou být všechny vrcholy, které tento vrchol mohou otevřít. (Tento vrchol mohu otevřít i "ručně", tzn. že jej zkrátka zvolím za startovní.)

Nyní předpokládejme, že existují alespoň dva volné vrcholy. Mohu zvolit nějaký vrchol, který by otevřel oba? Ne, jelikož každý vrchol prozkoumávám jenom v rámci jednoho BFS, a tak by někdy v průběhu algoritmu muselo dojít k přepsání jednoho volného vrcholu na prozkoumaný, což je spor. $\square$

Složitost: Z každého vrcholu procházím sousedy pouze jednou, takže složitost odpovídá složitosti BFS, čili $\Theta (n+m)$.