navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m33pal:uloha2 [2009/10/09 13:47] smoky |
courses:a4m33pal:uloha2 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| ==== 2. ÚLOHA ==== | ==== 2. ÚLOHA ==== | ||
| Nepostradatelný kanál | Nepostradatelný kanál | ||
| + | |||
| + | [[http://cmp.felk.cvut.cz/cmp/courses/a4m33pal/task.php?task=mosty|Zadání]] | ||
| + | |||
| + | Limit: 2s | ||
| + | |||
| + | [[http://www.algoritmy.net/article/1525/Nepostradatelny-most|Řešení na Algoritmy.net]] | ||
| Jak na to: | Jak na to: | ||
| Řádek 8: | Řádek 14: | ||
| * Všechny uzly při návratu z rekurze jsou v cyklu (a hrany samozřejmě také) až do uzlu, který odpovídá některému v seznamu ťuknutých (implementace: při návratu ze seznamu odeberu uzel, kterým se aktuálně vracím, pokud je seznam neprázdý, tak je pořád v nějakém cyklu)...ťuknutí na CLOSED netřeba řešit (větev byla zpracována z druhé strany (je to přístup z opačné strany do cyklu, který byl vyřešen návratem z OPEN uzlu)) | * Všechny uzly při návratu z rekurze jsou v cyklu (a hrany samozřejmě také) až do uzlu, který odpovídá některému v seznamu ťuknutých (implementace: při návratu ze seznamu odeberu uzel, kterým se aktuálně vracím, pokud je seznam neprázdý, tak je pořád v nějakém cyklu)...ťuknutí na CLOSED netřeba řešit (větev byla zpracována z druhé strany (je to přístup z opačné strany do cyklu, který byl vyřešen návratem z OPEN uzlu)) | ||
| * Tímto postupem se označí všechny hrany v cyklech, zbylé jsou nepostradatelné | * Tímto postupem se označí všechny hrany v cyklech, zbylé jsou nepostradatelné | ||
| + | |||
| + | |||
| + | ---- | ||
| Řádek 20: | Řádek 29: | ||
| Algoritmus je tedy pouhou modifikací procházení do hloubky a má i stejnou časovou a paměťovou složitost O(N + M). Zde jsou důležité části programu: | Algoritmus je tedy pouhou modifikací procházení do hloubky a má i stejnou časovou a paměťovou složitost O(N + M). Zde jsou důležité části programu: | ||
| + | <code pascal> | ||
| var Hladina, Spojeno: array[1..MaxN] of Integer; | var Hladina, Spojeno: array[1..MaxN] of Integer; | ||
| DvojSouvisle: Boolean; | DvojSouvisle: Boolean; | ||
| Řádek 53: | Řádek 62: | ||
| ... | ... | ||
| end. | end. | ||
| + | </code> | ||
| - | |||
| - | bohuzel nevim jak udelat, aby to ten kod tady takle nezprznilo ... | ||
| ~~DISCUSSION~~ | ~~DISCUSSION~~ | ||
