Code Submission Evaluation System Login

Datatähti 2018 loppu

Start:2018-01-18 12:15:00
End:2018-01-18 17:15:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2018 loppu - TietoverkkoCSES - Tietoverkko

Tietoverkko

Time limit:1.00 s
Memory limit:512 MB

Syrjälän tietoverkossa on $n$ tietokonetta, joiden välillä on $n$ yhteyttä. Tällä hetkellä on mahdollista lähettää viesti minkä tahansa kahden koneen välillä.

Tehtäväsi on laskea, moniko yhteyksistä on välttämätön: jos yhteyden poistaa, niin jonkin kahden koneen välillä ei enää voi lähettää viestiä.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: tietokoneiden määrä. Koneet on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $n$ riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: koneiden $a$ ja $b$ välillä on yhteys.

Kahden koneen välillä on enintään yksi yhteys, ja mistään koneesta ei ole yhteyttä itseensä.

Tuloste

Tulosta yksi kokonaisluku: välttämättömien yhteyksien määrä.

Esimerkki

Syöte:
7
1 2
2 3
2 4
4 5
2 5
5 6
6 7


Tuloste:
4

Selitys: Välttämättömät yhteydet ovat $(1,2)$, $(2,3)$, $(5,6)$ ja $(6,7)$.

Osatehtävä 1 (28 pistettä)
Osatehtävä 2 (72 pistettä)