Editorial for Skakači

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: admin

Posmatrajmo jednu komponentu grafa (skup povezanih čvorova):

  • Ukoliko postoji bar jedan ciklus sa neparnim brojem čvorova, možemo zaraziti sve servere iz cele komponente tako što odaberemo za početni bilo koji server koji se nalazi u neparnom ciklusu.
  • Ukoliko ne postoji nijedan ciklus neparne dužine (tj. ukoliko komponenta čini bipartitivni graf), i komponenta ima više od 2 čvora, možemo ga napraviti dodavanjem tačno jedne grane (npr. možemo izabrati bilo koji čvor koji ima 2 suseda, i povezati ta dva njegova suseda da bismo dobili ciklus od 3 čvora). Kada napravimo ciklus neparne dužine, opet možemo zaraziti sve servere iz te komponente kao što je opisano u prvoj stavci.

Da bismo zarzili celu mrežu, za početak svi čvorovi moraju biti povezani, odnosno graf mora imati samo jednu komponentu. Ukoliko graf ima K komponenti, da bismo ih sve povezali, neophodno nam je bar K-1 grana. U ovom slučaju, nije bitan način povezivanja. Ukoliko je u nekoj od komponenti postojao ciklus neparne dužine, taj ciklus postoji i dalje, pa sada vidimo da možemo zaraziti sve čvorove u celom grafu. Ukoliko nije postojala takva komponenta, onda moramo dodati bar još jednu granu da bismo napravili neparan ciklus.

Dakle, rešenje je K-1 ili K u zavisnosti od navedenih slučajeva. Zadatak je preuzet sa \texttt{Moscow} \texttt{Autumn} \texttt{Workshop} \texttt{2019} \texttt{Day} \texttt{1}, takmičenje \texttt{Welcome} \texttt{Contest} \texttt{from} \texttt{Asia}.

Comments


  • 0
    Nikola1234567  commented on April 5, 2020, 8:51 p.m.

    Test primer gde je ulaz
    3 2
    1 2
    2 3

    Zasto se ne zarazi cela mreza ako krenemo od 1 ovako 1->2->3 ?


    • 1
      admin  commented on April 5, 2020, 9:39 p.m. ← edited

      Nakon što server bude zaražen, dalje se zarazuju svi susedi njegovih suseda. To znači da ako zarazimo server 1, sledeći će biti zaražen samo još server 3 (2 će ostati nezaražen).