Jedná se o úlohu hledání Eulerovského tahu v zadaném grafu. Nejdříve je potřeba ověřit zda-li je graf opravdu Eulerovský.

Potřebné info naleznete na stránce: http://www.algoritmy.net/article/33838/Cycle-finding

Pro reprezentaci dat jsou asi nejlepší spojové seznamy. Pak má algoritmus opravdu lineární asymptotickou složitost.

By stradja3: Udělal jsem to pomocí té rekurze s tím, že když je to orientovaný graf tak si neustále aktualizuju vstupní a výstupní stupně pro každý uzel, abych náhodou předčasně nevlezl do koncového uzlu (který má výstupní stupeň 0). A funguje to. Problém je, že mi to počítá pomalu - pouze 5/10. Jakým způsobem se to udělá přes ty spojové seznamy?

By milanec: Já mám vrchol - ten má nějaké číslo a linkedList čísel vrcholů, do kterých má orientovanout hranu (tzn. vedou-li z vrcholu 2 do vrcholu dvě hrany do 4, jedna do 1 a jedna do 0, má linked list hodnoty - 4,4,1,0. Find mám stejný jako v přednáškách. Namísto push(new edge(from,to)) mám push(new int[]{from,to})… když jsem tam měl objekt, tak jsem těžce nestíhal. — Milan Černil 2013/10/13 23:17

By stradja3: A jak řešíš to, abys předčasně nevlezl do koncového uzlu, který má výstupní stupeň v danou chvíli 0 (pokud měl třeba 1 a už jsme ho jednou prošli)? Já to udělal podle tebe - mám u každého uzlu seznam následovníků a ty procházím do hloubky. Ale udržuju si informaci o výstupním stupni toho koncového uzlu. Když na něj narazím a ten stupeň je 0, tak ho v tom seznamu následovníků přesunu úplně na konec. Tím zaručím, že do něj vlezu až na závěr. Vypadá to jednoduše a jasně, jenže mi to u poloviny testovacích dat na webu hází špatné řešení nebo segmentation fault, takže tam mám nějakou chybu a nemůžu na ni přijít..

By milanec: Máš teda 2 situace

• Buď sudé stupně u všeho - je jedno kde začneš
• 2 s lichým - musíš začít u toho, který má více výstupních vrcholů

Já to dělám tak, že při načítání u všech uzlů mám field stupeň. Pokud do něj vede hrana, přidám jedničku, pokud vychází hrana, odeberu 1. Tím pádem najdeš výchozí tím, že bude mít stupeň -1. Takže si pak projedeš všechny vrcholy a tím, že najdeš ten s -1, tak víš, že začneš prohledávat cestu od něj. Udržuji si i nějaký count, kolik jsem jich našel - když jich najdu víc, tak nemá řešení samozřejmě :) Pokud takový nemám, tak jedu klasicky odkud chci. A do toho druhého lichého to vleze samo :) — Milan Černil 2013/10/15 00:12

By stradja3: tak 9/10 u test06 mám špatné řešení, nevím co tam je jinak oproti ostatním variantám. Píšou, že je to „random directed multigraph“. Nicméně teď už to asi nedávám.. Kdyby se sem náhodou ještě někdo podíval - nevíte čím by to mohlo být?