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>

1. Citirea datelor de intrare

with open('adiacenta1.in', 'r') as f:

   muchii = [list(map(int, linie.split())) for linie in f]

1. Determinăm numărul de vârfuri ale grafului

n = max(max(muchie) for muchie in muchii)

1. Inițializăm matricea de adiacență cu 0

adiacenta = [[0 for _ in range(n)] for _ in range(n)]

1. Parcurgem fiecare muchie

for muchie in muchii:

   i, j = muchie
   # Adăugăm muchia în matricea de adiacență
   adiacenta[i-1][j-1] = 1
   adiacenta[j-1][i-1] = 1

1. Afișăm matricea de adiacență

with open('adiacenta1.out', 'w') as f:

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

</syntaxhighlight>