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 graf_completIN.txt conţine pe prima linie numărul de grafuri G. Pentru fiecare dintre cele G grafuri se dă n și apoi matricea de adiacență, formată din n linii și n coloane.

Date de ieşire

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

Restricţii şi precizări

• 1 ≤ G ≤ 5
• 1 ≤ n ≤ 50

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

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