Rezolvare PBinfo #3147

Cerința

Se dă lista de muchii ale unui graf neorientat, conex, planar. Determinați numărul de fețe ale acestuia dacă este desenat astfel încât 2 muchii nu se intersectează.

O față este o regiune înconjurată de muchii.

Date de intrare

Se vor citi repetat de la tastatură muchiile grafului.

Date de ieșire

Programul va afișa pe ecran numărul de fețe ale grafului.

Restricții și precizări

• Ca și față, este considerată și regiunea exterioară, infinit de mare, a grafului.
• Numărul de muchii va fi mai mic decât 1.000.000.

Exemplu:

Intrare

1 2
2 3
3 4
4 1

Ieșire

2

Explicație

Graful se poate desena sub forma unui pătrat. Are doar o față, la care se adaugă și regiunea exterioară.