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

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)))

# Citim datele de intrare
n = int(input("Introduceti n: "))
k = int(input("Introduceti k: "))

# 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)