Page 15 - MATINF Nr.2

Concursul de Informatic˘a Programming Day 15

un num˘ar maxim de grupuri de localit˘at , i ˆıntre care se poate circula direct pe s , osele sau folosind
localit˘at , i intermediare.

Restrict , ii s , i preciz˘ari

1. 1 ≤ num˘arul de localit˘at , i ≤ 10000
2. 1 ≤ w ≤ 300
3. Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 20% din punctaj
4. Toate codurile localit˘at , ilor formeaz˘a un s , ir de numere consecutive ce ˆıncepe cu 1

Exemple

insule.in insule.out Explicat , ie
1 1 0 3 p = 1
3 4 Prima insul˘a cont , ine localit˘at , ile cu codurile
3 1 7 4 1, 4, 7 s , i o s , osea [1, 4].
1 2 A doua insul˘a are o singur˘a localitate cu codul
4 8 3 6 5 2 s , i zero s , osele.
1 4 A treia insul˘a cont , ine localit˘at , ile cu codurile
8 3 3, 5, 6, 8 s , i 3 s , osele: [8, 3], [5,8], [3,5].
5 8
3 5
insule.in insule.out Explicat , ie
2 1 3 p = 2
3 4 Prima insul˘a cont , ine localit˘at , ile cu codurile
3 1 7 4 1, 4, 7 s , i o s , osea [1, 4].
1 2 A doua insul˘a are o singur˘a localitate cu codul
4 8 3 6 5 2 s , i zero s , osele.
1 4 A treia insul˘a cont , ine localit˘at , ile cu codurile
8 3 3, 5, 6, 8 s , i 3 s , osele: [8, 3], [5,8], [3,5].
5 8 Prima insul˘a cont , ine dou˘a grupuri de localit˘at , i
3 5 cu conexiune pe s , osele {1, 4} si {7}.
A doua insul˘a cont , ine un singur grup
cu o localitate {2}.
A treia insul˘a cont , ine dou˘a grupuri de
localit˘at , i cu conexiune pe s , osele {3, 8,5} si {6}.
Insulele 1 s , i 3 au un num˘ar maxim
de grupuri cu conexiune pe s , osele.

Timp maxim de execut , ie: 0.4 secunde/test.
Memorie total˘a disponibil˘a 4 MB, din care 2 MB pentru stiv˘a.
Doru Constantin, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti

Solut , ie
Pentru rezolvarea problemei trebuie s˘a construim un graf neorientat ˆın care nodurile sunt
localit˘at , i, iar muchiile sunt s , osele. Memorarea grafului se va face folosind liste de adiacent , ˘a.
Pentru fiecare localitate vom ret , ine ˆıntr-un vector insula c˘areia ˆıi apart , ine (insula[x] = i, dac˘a x
ˆ
este pe insula i). In momentul ˆın care se citesc perechile de localit˘at , i care alc˘atuiesc s , osele se
actualizez˘a componentele unui vector ce ret , ine num˘arul de s , osele din fiecare insul˘a (ˆın C++