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

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