4072 - Graf Partial 5

Cerinţa

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n și un număr natural k. Din acest graf se elimină toate muchiile care au ambele extremități în vârfuri de grad mai mare sau egal cu k. Să se afișeze matricea de adiacență a grafului parțial obținut.

Date de intrare

Fişierul de intrare graf_partial_5IN.txt conţine pe prima linie numărul n, reprezentând numărul de vârfuri ale grafului și numărul k. 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_5OUT.txt va conţine 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 < k < n ≤ 100
• 1 ≤ i , j ≤ n
• muchiile se pot repeta în fișierul de intrare

Exemplul 1

graf_partial_5IN.txt

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

graf_partial_5OUT.txt

0 1 0 1 0 0 
1 0 0 0 1 1 
0 0 0 0 0 1 
1 0 0 0 1 0 
0 1 0 1 0 0 
0 1 1 0 0 0 

Explicație

Se elimină muchiile (2 3), (4 3), (2 4) deoarece vârfurile 2, 3 și 4 au gradul mai mare sau egal cu 3.

Exemplul 2

graf_partial_5IN.txt

1000 1000

graf_partial_5OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def citeste_input(cale_fisier):

   with open(cale_fisier, 'r') as fisier:
       n, k = map(int, fisier.readline().split())
       muchii = [tuple(map(int, linie.split())) for linie in fisier]
   return n, k, muchii

def verifica_restrictii(n, k, muchii):

   if not (1 < k < n <= 100):
       return False
   for muchie in muchii:
       if not (1 <= muchie[0] <= n and 1 <= muchie[1] <= n):
           return False
   return True

def construieste_matrice_adiacenta(n, muchii):

   matrice = [[0] * n for _ in range(n)]
   for muchie in muchii:
       matrice[muchie[0] - 1][muchie[1] - 1] = 1
       matrice[muchie[1] - 1][muchie[0] - 1] = 1
   return matrice

def elimina_muchii_grad_inalt(matrice, k):

   grade = [sum(rand) for rand in matrice]
   for i in range(len(matrice)):
       for j in range(len(matrice[i])):
           if grade[i] >= k and grade[j] >= k:
               matrice[i][j] = matrice[j][i] = 0
   return matrice

def scrie_output(cale_fisier, matrice):

   with open(cale_fisier, 'w') as fisier:
       for rand in matrice:
           fisier.write(' '.join(map(str, rand)) + '\n')

if __name__ == "__main__":

   fisier_input = "graf_partial_5IN.txt"
   fisier_output = "graf_partial_5OUT.txt"

   n, k, muchii = citeste_input(fisier_input)

   if not verifica_restrictii(n, k, muchii):
       with open(fisier_output, 'w') as fisier:
           fisier.write("Datele nu corespund restrictiilor impuse")
   else:
       matrice_adiacenta = construieste_matrice_adiacenta(n, muchii)
       matrice_modificata = elimina_muchii_grad_inalt(matrice_adiacenta, k)
       scrie_output(fisier_output, matrice_modificata)

</syntaxhighlight>