Page 17 - MATINF Nr. 11-12

a
Concursul de Informatic˘ Programming Day 17

Restrict , ii s , i preciz˘ari

1. 3 ≤ n ≤ 5000;
2. num˘arul de componente conexe cu cel put , in dou˘a noduri este cel mult 500;
3. coordonatele punctelor sunt numere naturale ≤ 100000.
a
4. Pentru rezolvarea corect˘ a cerint , ei 1 se vor acorda 20 de puncte.
a
5. Pentru rezolvarea corect˘ a cerint , ei 2 se vor acorda 80 de puncte.
Exemplu

componente.in componente.out
1 3
10 5
60 20
10 0
0 40
0 0
60 0
10 20
20 0
0 20
100 1000
200 2000
3 8
1 5
8 6
2 7
8 4
2 50
10 5
60 20
10 0
0 40
0 0
60 0
10 20
20 0
0 20
100 1000
200 2000
3 8
1 5
8 6
2 7
8 4

Explicat , ie

Pentru cerint , a 1 sunt 3 componente conexe cu cel put , in dou˘a noduri. Astfel avem:
componenta conex˘ cu muchia: [1,5];
a