主页 / 问题 / 1535087
Accepted
Настя
Asked:2023-08-10 00:05:45 +0000 UTC2023-08-10 00:05:45 +0000 UTC

图，使用邻接矩阵计算孤立的顶点，代码给出了错误的答案

  • 772

解决了以下问题：

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

Входные данные
В первой строке вводится количество городов на карте 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

2 个回答

  1. Best Answer

    系统不接受答案，因为您、我和本网站的其他参与者都假设该图的矩阵是对称的。这是对术语“图”的自然假设，没有任何限定。然而，问题的编译者有不同的想法。

    此代码通过了所有测试：

    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)
    • 2

  2. 运行tio

    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)
    • 0

相关问题