Elektriskās shēmas barošana

ID: elshbaro
Grūtība: 3/5
Laika limits: 1

Uzdevums

Elektriskās shēmas elementi izvietoti uz izolējoša materiāla plates. Elementu savienojumi ir izveidoti taisnu celiņu veidā. Ja diviem celiņiem ir kopīgs punkts, tad šajā punktā ir elektrisks kontakts.

Lai shēmas elementiem pieslēgtu barošanu, jāpanāk, lai barošana būtu pieslēgta visiem celiņiem un tāpēc dažu celiņu galapunkti jāsavieno ar barošanas bloku.

Uzrakstiet programmu, kas nosaka, kāds mazākais celiņu galapunktu skaits jāpieslēdz barošanas blokam, lai visi shēmas elementi saņemtu barošanu!

 

Ievaddati

Teksta faila elshbaro.dat pirmajā rindā dots naturāls skaitlis - shēmas celiņu skaits N (1≤N≤1000). Katrā no nākošajām N faila rindām doti četri veseli skaitļi x1 y 1 x2 y2 , kas apzīmē viena celiņa gala punktu (x 1,y1) un (x2,y2) koordinātas. Visas koordinātas ir veseli nenegatīvi skaitļi, kas nepārsniedz 1000. Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumsibols.

 

Izvaddati

Teksta faila elshbaro.rez vienīgajā rindā jāizvada naturāls skaitlis - mazākais celiņu galapunktu skaits, kas jāsavieno ar barošanas avotu.

 

Piemērs

elshbaro.datelshbaro.rez
3
1 2 4 2
1 1 2 3
3 1 3 2
1

  Piezīme: Tā kā visi celiņi ir savā starpā savienoti, barošanas bloku pietiek pieslēgt jebkura viena celiņa galapunktam.

Atsauces

Uzdevums izmantots Igaunijas informātikas olimpiādē 2004.gadā
© 2001-2002 olimps! http://www.lio.lv/olimps/