0431 - Graf Complet
De la Universitas MediaWiki
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()