Vizualizare sursă pentru „3147 - Fete Graf”

= 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.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= 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 <code>1.000.000</code>.
*
=Exemplul 1:=
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ă.

== Exemplul 2: ==
Intrare
 10000000
 1000000000000000
Ieșire
 Nu corespunde restricțiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restricții(numar_varfuri, numar_muchii):
    return 0 < numar_varfuri < 1000000 and 0 < numar_muchii < 1000000

def numar_fețe(numar_varfuri, numar_muchii):
    # Folosim formula lui Euler pentru grafuri planare: V - E + F = 2
    # Deoarece graful este conex, V = E + 2, deci substituim în formulă.
    # Obținem E + 2 - E + F = 2, și astfel F = 2.
    return 2

def main():
    try:
        numar_varfuri = int(input("Introduceți numărul de vârfuri ale grafului: "))
        numar_muchii = int(input("Introduceți numărul de muchii ale grafului: "))

        if not verificare_restricții(numar_varfuri, numar_muchii):
            print("Nu corespunde restricțiilor impuse.")
            return

        numar_muchii_introduse = 0
        while numar_muchii_introduse < numar_muchii:
            input_muchie = input(f"Introduceți o muchie sub forma x y (muchiile introduse: {numar_muchii_introduse}/{numar_muchii}): ")

            if ' ' in input_muchie:
                v1, v2 = map(int, input_muchie.split())

                if 0 < v1 <= numar_varfuri and 0 < v2 <= numar_varfuri:
                    numar_muchii_introduse += 1
                else:
                    print(f"Vârfurile muchiei trebuie să fie între 1 și {numar_varfuri} inclusiv.")
            else:
                print("Introduceți o pereche validă de vârfuri sub forma x y.")

        rezultat = numar_fețe(numar_varfuri, numar_muchii)
        print(f"Numărul de fețe al grafului este: {rezultat}")

    except ValueError:
        print("Introduceți numere valide pentru numărul de vârfuri și muchii.")

if __name__ == "__main__":
    main()

</syntaxhighlight>