0422 - Graf Partial 2

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 o extremitate într-un vârf de grad maxim. Să se determine numărul de muchii eliminate și să se afișeze matricea de adiacență a grafului parțial obținut.

Date de intrare

Fişierul de intrare graf_partial_2in.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_partial_2out.txt va conţine pe prime linie numărul de muchii eliminate, iar pe următoarele linii matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

Restricții și precizări

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

Exemplul 1

graf_partial_2in.txt

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

graf_partial_2out.txt

Datele de intrare corespund restrictiilor impuse.
4
0 1 0 0 0 0 
1 0 0 0 0 1 
0 0 0 0 0 0 
0 0 0 0 1 1 
0 0 0 1 0 0 
0 1 0 1 0 0 

Explicație

Se elimină muchiile (2 3), (4 3), (5 3), (3 6).

Exemplul 2

graf_partial_2in.txt

jgirjiurmgrog

graf_partial_2out.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat

def validare(n_validare, muchii_validare):

   # Verificăm dacă n este în intervalul 1-100
   if n_validare < 1 or n_validare > 100:
       raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 1-100
   for muchie_validare in muchii_validare:    # Parcurgem lista de muchii
       # Verificăm dacă valoarea absolută a fiecărui vârf este în intervalul 1-n
       if (abs(muchie_validare[0]) < 1 or abs(muchie_validare[0]) > n_validare 
               or abs(muchie_validare[1]) < 1 or abs(muchie_validare[1]) > n_validare):
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

1. Funcția elimina_muchii elimină muchiile cu o extremitate într-un vârf de grad maxim

def elimina_muchii(n_elimina, muchii_elimina):

   # Calculăm gradele vârfurilor
   grade = [0] * (n_elimina + 1)
   for muchie_eliminare in muchii_elimina:
       grade[muchie_eliminare[0]] += 1
       grade[muchie_eliminare[1]] += 1
   # Determinăm gradul maxim
   grad_max = max(grade)
   # Eliminăm muchiile cu o extremitate într-un vârf de grad maxim
   muchii_eliminate_ = 0
   muchii_noi_creat = []
   for muchie_eliminare in muchii_elimina:
       if grade[muchie_eliminare[0]] == grad_max or grade[muchie_eliminare[1]] == grad_max:
           muchii_eliminate_ += 1
       else:
           muchii_noi_creat.append(muchie_eliminare)
   return muchii_eliminate_, muchii_noi_creat

if __name__ == '__main__':

   file_in = open("graf_partial_2in.txt", "r")
   file_out = open("graf_partial_2out.txt", "w")

   try:
       # Citim numărul de vârfuri
       n_main = int(file_in.readline())
       # Citim muchiile
       muchii_main = [list(map(int, linie.split())) for linie in file_in.readlines()]
       # Validăm datele de intrare
       validare(n_main, muchii_main)
       # Eliminăm muchiile cu o extremitate într-un vârf de grad maxim
       muchii_eliminate, muchii_noi = elimina_muchii(n_main, muchii_main)
       # Scriem numărul de muchii eliminate în fișierul de ieșire
       file_out.write(str(muchii_eliminate) + '\n')
       # Scriem matricea de adiacență a grafului parțial obținut în fișierul de ieșire
       matrice_adiacenta = [[0] * n_main for _ in range(n_main)]
       for muchie in muchii_noi:
           matrice_adiacenta[muchie[0]-1][muchie[1]-1] = 1
           matrice_adiacenta[muchie[1]-1][muchie[0]-1] = 1
       for linie in matrice_adiacenta:
           file_out.write(' '.join(map(str, linie)) + '\n')

   # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
   # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>