Задача №460. Проверка на неориентированность

По заданной квадратной матрице n×n из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

Входные данные

На вход программы поступает число n (1≤n≤100) – размер матрицы, а затем n строк по n чисел, каждое из которых равно 0 или 1, – сама матрица.

Выходные данные

Выведите «YES», если приведенная матрица может быть матрицей смежности простого неориентированного графа, и «NO» в противном случае.

Примеры

входные данные

5

0 0 1 0 0

0 0 1 0 1

1 1 0 0 0

0 0 0 0 0

0 1 0 0 0

выходные данные

YES

Мой код:

n = int(input())
a = []
b = []
for i in range(n):
    f = list(map(int, input().split()))
    a.append(f)
    g = f[::]
    b.append(g)
for i in range(n):
    for j in range(i+1, n):
        a[i][j], a[j][i] = a[j][i], a[i][j]
if b == a:
    print('YES')
else:
    print('NO')

Проблема в том, что программа на некоторых тестах не проходит, выводит неправильный ответ. Я сама мучалась над этой проблемой, но безрезультатно. Подскажите, где ошибка?


Ответы (1 шт):

Автор решения: MBo

Транспонировать матрицу не обязательно, достаточно проверить, что a[i][j]==a[j][i]

Кроме того, раз граф простой, то нужно проверить, что в графе нет петель - все элементы на главной диагонали должны быть нулевые.

→ Ссылка