Editing 4072 - Graf Partial 5 (section)

= Explicație =
Se elimină muchiile <code>(2 3)</code>, <code>(4 3)</code>, <code>(2 4)</code> deoarece vârfurile <code>2</code>, <code>3</code> și <code>4</code> au gradul mai mare sau egal cu <code>3</code>.

== Exemplul 2 ==
<code>graf_partial_5IN.txt</code>
 1000 1000
<code>graf_partial_5OUT.txt</code>
 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>