0413 - Adiacenta 1

Cerinţa

Se dă lista muchiilor unui graf neorientat. Să se afișeze matricea de adiacență a grafului.

Date de intrare

Fiecare dintre liniile fișierului adiacenta1in.txt conține câte o pereche de numere i j, cu semnificația că există muchie între i și j.

Date de ieșire

Fişierul de ieşire adiacenta1out.txt va conţine n linii; pe fiecare dintre ele vor fi câte n valori separate prin exact un spațiu, reprezentând matricea de adiacență a grafului dat.

Restricţii şi precizări

• graful dat va avea cel mult 100 de vârfuri
• muchiile se pot repeta în fișierul de intrare
• numărul de vârfuri ale grafului va fi egal cu cea mai mare valoare din lista muchiilor

Exemplu

adiacenta1in.txt

1 4 
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4 

adiacenta1out.txt

Datele de intrare corespund restrictiilor impuse
0 1 1 1 0 
1 0 0 1 0 
1 0 0 1 1 
1 1 1 0 1 
0 0 1 1 0

adiacenta1in.txt

1 400
1 3 
3 5 
4 5 
2 4 
1 2 
4 2 
3 4 

adiacenta1out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def validare(muchii):

   n = max(max(muchie) for muchie in muchii)
   if not 1 <= n <= 100:
       return False, "Datele de intrare nu corespund restrictiilor impuse"
   return True, "Datele de intrare corespund restrictiilor impuse"

def main():

   with open('adiacenta1in.txt', 'r') as fin:
       muchii = [list(map(int, linie.split())) for linie in fin]

   valid, message = validare(muchii)
   with open('adiacenta1out.txt', 'w') as fout:
       fout.write(message + '\n')
       if not valid:
           return

       n = max(max(muchie) for muchie in muchii)
       adiacenta = [[0 for _ in range(n)] for _ in range(n)]
       for muchie in muchii:
           i, j = muchie
           adiacenta[i - 1][j - 1] = 1
           adiacenta[j - 1][i - 1] = 1

       for linie in adiacenta:
           fout.write(' '.join(map(str, linie)) + '\n')

if __name__ == "__main__":

   main()

</syntaxhighlight>