0420 - Graf Partial

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Din acest graf se elimină toate muchiile cu proprietatea că ambele extremități au aceeași paritate. Să se determine câte muchii va avea graful parțial obținut.

Date de intrare

Fişierul de intrare graf_partialIN.txt conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului. Fiecare dintre următoarele linii conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieşire

Fişierul de ieşire graf_partialOUT.txt va conţine pe prima linie numărul M de muchii ale grafului parțial obținut.

Restricţii şi precizări

• 1 ≤ n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplul 1

graf_partialIN.txt

5
1 4
3 5
2 3
2 1
4 2
3 2
1 3

graf_partialOUT.txt

3

Explicație

Se elimină muchiile (3 5), (4 2), (1 3). Graful parțial obținut va avea muchiile (1 4), (2 3) și (2 1).

Exemplul 1

graf_partialIN.txt

1000

graf_partialOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def verificare_restricții(n, muchii):
    # Verifică restricția 1: 1 ≤ n ≤ 100
    if not (1 <= n <= 100):
        return False

    # Verifică restricția 2: 1 ≤ i, j ≤ n pentru fiecare muchie
    for muchie in muchii:
        i, j = muchie
        if not (1 <= i <= n) or not (1 <= j <= n):
            return False

    return True

def elimina_muchiile_paritare(n, muchii):
    graf_partial = set()

    for muchie in muchii:
        i, j = muchie
        if i % 2 != j % 2:
            graf_partial.add(tuple(sorted(muchie)))

    return graf_partial

def main():
    # Citeste datele de intrare
    with open("graf_partialIN.txt", "r") as f:
        n = int(f.readline().strip())
        muchii = [list(map(int, line.strip().split())) for line in f]

    # Verifică restricțiile
    if not verificare_restricții(n, muchii):
        # Scrie mesajul în fișierul de ieșire
        with open("graf_partialOUT.txt", "w") as f:
            f.write("Datele nu corespund restrictiilor impuse\n")
        return

    # Elimina muchiile cu extremitati de aceeasi paritate
    graf_partial = elimina_muchiile_paritare(n, muchii)

    # Scrie doar numarul de muchii in fisierul de iesire
    with open("graf_partialOUT.txt", "w") as f:
        f.write(str(len(graf_partial)) + "\n")

if __name__ == "__main__":
    main()