Задача №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 шт):
Транспонировать матрицу не обязательно, достаточно проверить, что a[i][j]==a[j][i]
Кроме того, раз граф простой, то нужно проверить, что в графе нет петель - все элементы на главной диагонали должны быть нулевые.