Editing 0431 - Graf Complet

= Cerinţa =
Se dau mai multe grafuri neorientate, prin matricea de adiacență. Să se verifice despre fiecare graf dacă este complet.

= Date de intrare =
Fişierul de intrare <code>graf_completIN.txt</code> conţine pe prima linie numărul de grafuri <code>G</code>. Pentru fiecare dintre cele <code>G</code> grafuri se dă <code>n</code> și apoi matricea de adiacență, formată din <code>n</code> linii și <code>n</code> coloane.

= Date de ieşire =
Fişierul de ieşire <code>graf_completOUT.txt</code> va conţine <code>G</code> linii. Pe fiecare dintre ele se va afla mesajul <code>DA</code> sau <code>NU</code>, după cum graful corespunzător este sau nu complet.

= Restricţii şi precizări =

* <code>1 ≤ G ≤ 5</code>
* <code>1 ≤ n ≤ 50</code>

== Exemplul 1 ==
graf_completIN.txt:

2

3

0 1 1

1 0 1

1 1 0

4

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

graf_completOUT.txt:

DA

NU

== Exemplul 2 ==
graf_completIN.txt:

99

3

0 1 1

1 0 1

1 1 0

4

0 1 1 1

1 0 0 1

1 0 0 1

1 1 1 0

Output:

Restrictii neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def este_graf_complet(matrice_adiacenta):
    n = len(matrice_adiacenta)
    for i in range(n):
        for j in range(n):
            if i != j and matrice_adiacenta[i][j] == 0:
                return False
    return True

def verifica_restrictii(G, n):
    return 1 <= G <= 5 and 1 <= n <= 50

def main():
    with open("graf_completIN.txt", "r") as f_in, open("graf_completOUT.txt", "w") as f_out:
        G = int(f_in.readline().strip())

        for _ in range(G):
            n = int(f_in.readline().strip())
            if not verifica_restrictii(G,n):
                print("Restrictii neindeplinite")
                return
            matrice_adiacenta = []
            for _ in range(n):
                linie = list(map(int, f_in.readline().split()))
                matrice_adiacenta.append(linie)

            rezultat = "DA" if este_graf_complet(matrice_adiacenta) else "NU"
            f_out.write(rezultat + "\n")

if __name__ == "__main__":
    main()

</syntaxhighlight>