0413 - Adiacenta 1
De la Universitas MediaWiki
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
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()