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

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()