# ADS B - Polosouvislý graf

Existuje-li mezi $u,v$ silná souvislost, pak stačí testovat polosouvislost pouze pro jeden z těchto vrcholů. Pokud bych tak provedl kondenzaci, výsledný graf již bude obsahovat pouze jednosměrné cesty.
Není-li takový graf ani slabě souvislý, pak je odpověď triviální. V opačném případě se jedná o DAG. Ten nebude polosouvislý v případě, bude-li se cesta ze zdrojové komponenty větvit.

Důkaz: Vezmu si dva vrcholy za větvením. Budu-li hledat cestu podle směru šipek, musí se v některém vrcholu cesty spojit. Jelikož však v takovém grafu není cyklus, musí obě šipky směřovat do daného vrcholu a nemohu tedy v cestě pokračovat. Naopak budu-li hledat cestu proti směru šipek, pak se dostanu k vrcholu, kde se cesta rozdělovala, a tak opět nemohu pokračovat dále. $\square$

To zároveň znamená, že se cesty ze zdrojových komponent nesmí ani spojovat. Požaduju-li slabou souvislost, pak výsledkem musí být pouze cesta. Tzn.: polosouvislý graf je takový, který je slabě souvislý a grafem komponent silné souvislosti je cesta.

Problém je v tom, že samotná kondenzace (kontrakce hran podle silné souvislosti) je náročná.
Mohu si však zaznamenat, z které komponenty jsem tuto komponentu objevil (což je pro DFS triviální záležitost). Navíc, objevím-li vrchol $v$ z vrcholu $u$, pak vrchol $u$ objevím z $v$ jen v případě, že leží ve stejné komponentě. Díky těmto informacím již mohu vytvořit graf komponent silné souvislosti (hrana $AB$ existuje, vede-li alespoň jeden vrchol z $A$ do vrcholu z $B$; obráceně nemůže, neboť vy vzniknul cyklus). Budu-li se držet algoritmu z Průvodce:

$1.$ Otočím orientaci hran v grafu.
$2.$ Spouštím DFS z neprozkoumaných vrcholů.
$3.$ Jakmile otevřu vrchol, poznačím si, odkud jsem jej otevřel.
$4.$ Uzavřené vrcholy vložím do zásobníku.
$5.$ Jsou-li všechny vrcholy uzavřeny, jdu dál. Jinak $\to 1.$
$6.$ Vyndám vrchol ze zásobníku. Nemám-li označeno, v jaké komponentě leží, provedu DFS a objevené vrcholy označím číslem komponenty.
$7.$ Není-li zásobník prázdný, $\to 5$. Jinak vytvoř prázdný (bezhranový) graf, kde vrcholy=komponenty.
$8.$ Pro každý vrchol zjisti, v jaké komponentě leží vrchol, který jej otevřel (otec - v $2$).
$9.$ Leží-li v jiné komponentě než momentální vrchol, vytvoř hranu otec$\to$momentální vrchol
$10.$ Jakmile jsou všechny vrcholy prozkoumány, zjisti, zdali je graf cesta. Pokud ano, graf je slabě souvislý.

Složitost: DFS je lineární s velikostí grafu; ačkoli jej musím spouštět vícekrát, jdu pouze přes neprozkoumané vrcholy. Zaznamenávání vstupu je lineárně závislé na počtu vrcholů, stejně tak jako konstrukce finálního grafu.