- Time limit: 1.00 s
- Memory limit: 512 MB
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ä)
- $2 \le n \le 100$
- $2 \le n \le 10^5$