Условие задачи:
Дан неориентированный невзвешенный граф. Для него вам необходимо найти количество вершин, лежащих в одной компоненте связности с данной вершиной (считая эту вершину).
Граф представлен в виде матрицы смежности.
Сразу же написал решение через поиск в глубину:
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))
- Запускаем функцию
dfs
на стартовой вершине - Добавляем ее в список посещенных
- Пробегаем по каждой вершине
- Проверяем соединена ли она с текущей и есть ли она в списке посещенных
- Если все ок, то запускаем в ней
dfs
- В конце считаем кол-во элементов в списке
visited
и выводим его
Программа выдает неправильный ответ на двух тестах. Ссылка на проверяющую систему
ЧЯДНТ?
(Я видел другие реализации, но хотел узнать в чем ошибка именно в моем коде)