4

Условие задачи:

Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин, лежащих в одной компоненте связности с данной вершиной (считая эту вершину).

Граф представлен в виде матрицы смежности.
Сразу же написал решение через поиск в глубину:

def dfs(v):
    visited.append(v)

    for i in range(n):
        if graph[v][i] == 1 and i not in visited:
            dfs(i)


n, s = map(int, input().split())
graph = [list(map(int, input().split())) for x in range(n)]

visited = []
dfs(s)

print(len(visited))
  1. Запускаем функцию dfs на стартовой вершине
  2. Добавляем ее в список посещенных
  3. Пробегаем по каждой вершине
  4. Проверяем соединена ли она с текущей и есть ли она в списке посещенных
  5. Если все ок, то запускаем в ней dfs
  6. В конце считаем кол-во элементов в списке visited и выводим его

Программа выдает неправильный ответ на двух тестах. Ссылка на проверяющую систему


ЧЯДНТ?

(Я видел другие реализации, но хотел узнать в чем ошибка именно в моем коде)

2

1 ответ 1

2
+50

Номер заданной вершины s задаётся в интервале 1 ≤ s ≤ n, то есть нумерция с единицы.

(Ошибку можно обнаружить, например, на графе из одной вершины)

1
  • 2
    то есть первый вызов надо делать так: dfs(s-1) 12 дек 2017 в 8:30

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.