Elektroinštalácia

3 akceptované riešenia za plný počet bodov

  • 0.16-0.24 s (2x Java)
  • 0.15 s (1x Python 3)

Každá izba zvlášť

  • spustíme prehľadávanie do hĺbky a očíslujeme vrcholy podľa neho (pre každý vrchol, okrem rozvodnej skrine, poznáme rodiča)
  • zo všetkých zásuviek v jednej izbe spustíme prechádzanie ku rozvodnej skrini (koreňu) tak, aby sa vrcholy neopakovali.
  • zopakujeme pre každú izbu
  • pre každú hranu si môžeme pamätať koľkokrát sme ňou prechádzali - určí nam to maximálny počet káblov, a teda potrebnú šírku lišty

Príklad 2 3 4 1 1 obr

Všetko jedným prehľadávaním

  • pri vracaní sa späť zaktualizujeme potrebnú dĺžku kábla a zoznam miestností, ktoré sú z daného vrchola zapojené

image.png

Hinty

  • pri spájaní zoznamu miestností je potrebné aktualizovať ako množinu (miestnosť je napájaná z rodiča, ak aspoň jeden potomok napája zásuvku v danej izbe)
  • z rozvodnej skrine môžu ísť káble nezávislé na sebe, teda pre uvedený obrázok je maximálny počet káblov 4 (hrana 1-2).

Interornetizmus (mosty v grafe)

4 body do 30.04.2020 23:59
2 body do 05.05.2020 12:00