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 1.000.000.

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

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()