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 adiacenta1.in 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 adiacenta1.out 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

adiacenta1.in

1 4

1 3

3 5

4 5

2 4

1 2

4 2

3 4

adiacenta1.out

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

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>