4069 - Graf Complet

Cerința

Se dau două numere naturale n k. Considerăm graful complet cu n noduri, etichetate de la 1 la n. Din acesta eliminăm toate muchiile (i,j) cu proprietatea că i și j dau același rest la împărțirea cu k.

Afișati matricea de adiacență a grafului parțial obținut.

Date de intrare

Programul citește de la tastatură numerele n k.

Date de ieșire

Programul va afișa pe ecran matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a ecranului, elementele de pe fiecare linie fiind separate prin câte un spațiu.

Restricții și precizări

• 1 < k < n ≤ 100

Exemplul 1

Intrare

6 3

Ieșire

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

Exemplul 2

Intrare

50 101

consola

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def construieste_graf_partial(n, k):

   # Verificăm restricțiile impuse
   if not (1 < k < n <= 100):
       print("Datele nu corespund restrictiilor impuse")
       return None

   # Inițializăm matricea de adiacență cu 0
   matrice_adiacenta = [[0] * n for _ in range(n)]

   # Construim graful complet și eliminăm muchiile dorite
   for i in range(1, n + 1):
       for j in range(i + 1, n + 1):
           if i % k != j % k:
               # Dacă i și j au resturi diferite la împărțirea cu k, adăugăm muchia în graf
               matrice_adiacenta[i - 1][j - 1] = 1
               matrice_adiacenta[j - 1][i - 1] = 1

   return matrice_adiacenta

def afiseaza_matrice_adiacenta(matrice):

   # Afișăm matricea pe ecran
   for linie in matrice:
       print(" ".join(map(str, linie)))

1. Citim datele de intrare

n = int(input("Introduceti n: ")) k = int(input("Introduceti k: "))

1. Construim și afișăm matricea de adiacență, verificând restricțiile

graf_partial = construieste_graf_partial(n, k)

if graf_partial is not None:

   afiseaza_matrice_adiacenta(graf_partial)

</syntaxhighlight>