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

<syntaxhighlight lang="python3" line="1"> 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()

</syntaxhighlight>