2707 - Matad

Cerinţa

Dându-se o matrice de numere întregi cu dimensiune linii și dimensiune coloane, să se verifice dacă este sau nu matrice de adiacență asociată unui graf neorientat.

Date de intrare

Programul citește de la tastatură numărul dimensiune, iar apoi se citesc de pe dimensiune linii câte dimensiune numere naturale, separate prin spații, reprezentând elementele matricei.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare respectă cerințele impuse" daca se respecta datele de intrare iar in caz contrar se afiseaza mesajul “Datele de intrare nu respectă cerințele impuse” Programul va afișa pe ecran valoarea 1 dacă matricea este de adiacență, sau 0 dacă nu este matrice de adiacență.

Restricţii şi precizări

• 3 ⩽ dimensiune ⩽ 100

Exemplul 1

Intrare

4
0 1 1 0
1 0 0 0
1 0 0 1
0 0 1 0

Ieșire

Datele de intrare respectă cerințele impuse
1

Exemplul 2

Intrare

4
0 1 1 0
1 0 0 0
0 0 0 1
0 0 0 0

Ieșire

Datele de intrare respectă cerințele impuse
0

Rezolvare

<syntaxhighlight lang="python" line> def is_adjacency_matrix(matrix, dimensiune):

   # Verificăm dacă matricea are dimensiunea dimensiune x dimensiune
   if len(matrix) != dimensiune or any(len(row) != dimensiune for row in matrix):
       print("Datele de intrare nu respectă cerințele impuse")
       return 0

   # Verificăm condițiile pentru o matrice de adiacență
   for i in range(dimensiune):
       for j in range(dimensiune):
           # Condiția 1: Nu există bucle (diagonala principală trebuie să fie 0)
           if i == j and matrix[i][j] != 0:
               print("Datele de intrare nu respectă cerințele impuse")
               return 0

           # Condiția 2: Elementele matricei trebuie să fie doar 0 sau 1
           if matrix[i][j] not in {0, 1}:
               print("Datele de intrare nu respectă cerințele impuse")
               return 0

           # Condiția 3: Matricea trebuie să fie simetrică
           if matrix[i][j] != matrix[j][i]:
               print("Datele de intrare nu respectă cerințele impuse")
               return 0

   # Dacă toate condițiile sunt îndeplinite, matricea este o matrice de adiacență
   print("Datele de intrare respectă cerințele impuse")
   return 1

def main():

   # Citim dimensiunea matricei de la tastatură
   dimensiune = int(input())

   # Citim matricea de adiacență de la tastatură
   matrix = []

   for _ in range(dimensiune):
       row = list(map(int, input().split()))
       matrix.append(row)

   # Verificăm dacă matricea este o matrice de adiacență
   result = is_adjacency_matrix(matrix, dimensiune)

   # Afișăm rezultatul
   print(result)

if __name__ == "__main__":

   main()

</syntaxhighlight>