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

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)