Графы, подсчёт изолированных вершин с помощью матрицы смежности, код выдаёт неверный ответ

Рейтинг: 3Ответов: 2Опубликовано: 09.08.2023

решала следующую задачу:

На острове расположены несколько государств, изолированных 
друг от друга. У программиста Васи есть данные обо всех дорогах 
острова, заданные в виде весовой матрицы соответствующего графа, 
узлы которого – города, а веса рёбер – расстояния между ними. 
Напишите программу, которая определяет, сколько государств, 
состоящих из единственного города, находится на острове.

Входные данные
В первой строке вводится количество городов на карте N ( 1 ≤ N ≤ 1000 ).
 В следующих N строках записано по N чисел, разделённых пробелами – 
элементы весовой матрицы графа, который описывает схему дорог.

Выходные данные
Программа должна вывести номера всех государств, состоящих из одного 
города, в порядке возрастания. Нумерация начинается с единицы. Если 
таких городов нет, нужно вывести число 0.

Примеры
входные данные
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 0
0 0 0 0 0
выходные данные
4 5

Написала по ней код:

n=int(input()) 
a=[list(map(int, input().split())) for i in range(n)]
ans1=[]
for i in range(n):
    if len(set(a[i]))==1:
        ans1.append(i+1)
ans2=[] 
for i in range(n):
    q=0 
    for j in range(n):
        q+=a[j][i] 
    if q==0:
        ans2.append(i+1)
if len(ans1)==0 or len(ans2)==0:
    print(0) 
else:
    for i in ans1:
        if i in ans2:
            print(i, end=" ")

Но на трёх тестах проверяющей системы код выдаёт неверный ответ, помогите пожалуйста!!! Ссылка на задачу: https://informatics.msk.ru/mod/statements/view.php?id=83389&chapterid=479#1

python графы
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Система не принимает ответ так как вы, я и другие участники на этом сайте предположили что матрица графа симметричная. Это естественное предположение для термина "граф" без уточнений. Тем не менее составители задачи считают по другому.

Этот код проходит все тесты:

n = int(input())
a = [[int(w) for w in input().split()] for _ in range(n)]

answer = [
    i + 1
    for i in range(n)
    if all(a[i][j] == 0 and a[j][i] == 0 for j in range(n) if j != i)
]

if answer:
    print(*answer)
else:
    print(0)

Ещё один вариант. Сложность по памяти уменьшена до O(N):

n = int(input())

isolated = [True] * n

for i in range(n):
    for j, w in enumerate(map(int, input().split())):
        if w != 0 and i != j:
            isolated[i] = False
            isolated[j] = False

answer = [i + 1 for i in range(n) if isolated[i]]
if answer:
    print(*answer)
else:
    print(0)
▲ 0

tio.run

print(" ".join(map(str, (i+1 for i in range(int(input())) if not any(map(int, input().split()))))) or 0)

Если в графе разрешены петли, то немного хитрее: tio.run

print(" ".join(map(str, (i+1 for i in range(int(input())) if not any(int(x) and i != j for j,x in enumerate(input().split()))))) or 0)