Počítačová síť

Zadání

Limit: 2s

Jak na to:

1. Načíst vstup a uložit do listu hran. Je potřeba dávat pozor na to, že A→B je to stejné jako B→A. Mohou se tam také vyskytnout duplicitní nabídky, takže zachovat jenom tu s menší cenou
2. Seřadit hrany podle ceny, pokud jsou ceny stejné tak podle čísla první budovy
3. Inicializovat struktury na UNION-FIND - dvě pole:
   • „pole bossů“ - index je číslo budovy a obsah je kdo je boss budovy, na začátku je každý svůj boss
   • „pole hloubek“ - index je číslo budovy a obsah její hloubka, na začátku je hloubka 0
4. Procházet možné hrany od těch s nejmenších cenou a postupně je přidávat dokud jich nebude (počet budov-počet připojení k netu)
5. Nesmím ale přidat hranu, která by vytvořila cyklus - máme funkci můžuPřidatHranu(hrana), kterou řeší UNION-FIND:
   • pokud obě budovy z hrany mají stejného bosse, vzniknul by cyklus a vracím false
   • pokud obě budovy z hrany mají různého bosse, vracím true a přidávám hranu do dvou polí takto:
     • pokud hloubka bosse první budovy < hloubka bosse druhé budovy ⇒ boss první budovy je boss druhé budovy
     • pokud hloubka bosse první budovy > hloubka bosse druhé budovy ⇒ boss druhé budovy je boss první budovy
     • pokud hloubka bosse první budovy == hloubka bosse druhé budovy ⇒ boss druhé budovy je boss první budovy && zvyšuju hloubku u bosse první budovy o 1
6. Najít budovy, kam zavést interfernet, to už je easy:
   • Projdu pole bossů a uložím si tolik různých bossů, kolik mám zavést internetů
7. Všechno vypsat