# Mareš 7. 6. 2018

<{ForumPost(poster="Sedmikráska", timestamp=2018-06-07 20:53:25)}>
1. Algoritmus pro hledání silně souvislých komponent + složitosti + důkaz správnosti  
2. Součin čísel v lepším čase než O(n^2)  
3. V grafu, jehož hrany jsou ohodnoceny pravděpodobnostmi projití, najděte nejpravděpodobnější cestu, že se dostanete do cíle + složitosti  
4. V lexikografickém uspořádání prvků 1 až n najděte k-tou permutaci (nejlépe v lepším než kvadratickém čase)  
  
1. a 2. bylo řečeno na přednášce  
3. Dijsktra, ve kterém se místo vah hran počítá s -log(pravděpodobnost projití hrany)  
4. Číslo k převedeme do jeho faktoriálové reprezentace a z této reprezentace postupně od začátku vybíráme číslice, které reprezentují, kolikátý prvek z počáteční permutace 1 až n máme vzít - dá se zrychlit pomocí toho, že se ukládají prvky do stromu
<{/ForumPost}>