Postup řešení od samotných autorů je na webu předmětu, https://cw.fel.cvut.cz/wiki/_media/courses/a4m33pal/komment.pdf

===== Jak na to nejít =====

V dokumentu je uvedeno, že cyklus vzniknuvší otočením hrany h v DAG může být tvořen pouze uzly nacházejícím se mezi koncovými uzly hrany h (x,y) v topologickém uspořádání. Cyklus je vytvořen průnikem následníků x a předchůdců y.

Získat následníky (vznostně tranzitivní uzávěr) každého vrcholu lze pomocí modifikovaného Floyd Warshall algoritmu vynásobením matice sousedů (resp. několikanásobné iterací přes všechny prvky). Výhoda je pro husté grafy, čas je vždy téměř konstatní 0(n^3) při neoptimalizované verzi. Vznikne matice VxV, kde na řádku jsou následnící uzlu a ve sloupci jsou předchůdci. Nyní již stačí procházet uzly mezi x a y v topologickém uspořádání a zjišťovat, zda-li je uzel následníkem x a předchůdcem y.

Formálně je výsledek správně, ale časový limit pro úlohu nevystačí a ačkoliv se vrátí správné výsledky, body to nezaručí. Profilování kódu zjistí, 99% času se trávilo v rutině na výpočet matice "dostupnosti".


===== Můj postup (C/C++) =====

Myšlenka řešení je následující:
Proč budovat matici "dostupnosti" pro všechny uzly, když některé nás nebudou zajímat? Zjistí se až během výpočtu.

Postup:
  * Vytvoření topologického uspořádání
  * Pro každou hranu: 
      * Vezmi koncové uzly x a y
      * Najdi všechny uzly v topologickém uspořádání mezi x a y => označme to jako množina P(x,y)
      * Sjednoť x a P(x,y), tj. pro každý uzel x a z(koho čeho) P(x,y) vypočti pomocí DFS následníky a ulož do matice "dostupnosti". Je dobré si zapamatovat, že pro konkrétní uzel byli následníci    spočítány.
      * Iteruj přes uzly z P(x,y) a zjišťuj z matice "dostupnosti", zdali jsou následníci x a předchůdci y. Pokud ano, sčítej váhy a zjisti další údaje dle zadání úlohy





**Možné optimalizace:**

Při procházení seznamu hran a zjišťování cyklů nemá cenu hledat cyklus u uzlů, kterým po přehození hrany se d+ nebo d- sníží na 0, tedy buďto do nich nevede nebo z nich nevychází žádná hrana.

~~DISCUSSION~~