Задача 14: Обход в глубину

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

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

Входные данные:

В первой строке входных данных содержатся два числа: \(N\) и \(S\) \((1 ≤ N ≤ 100; 1 ≤ S ≤ N)\), где \(N\) – количество вершин графа, а \(S\) – заданная вершина. В следующих \(N\) строках записано по \(N\) чисел – матрица смежности графа, в которой \(0\) означает отсутствие ребра между вершинами, а \(1\) – его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

Выходные данные:

Выведите одно целое число – искомое количество вершин.

Решение:

n, s = map(int, input().split())

u = [[int(i) for i in input().split()] for _ in range(n)]

used = [False for _ in range(n)]
g = [[] for i in range(n)]
for i in range(n):
    for j in range(n):
        if u[i][j]:
            g[i].append(j)
            g[j].append(i)


def dfs(v):
    global used
    used[v] = True
    cnt = 1
    for i in g[v]:
        if not used[i]:
            cnt += dfs(i)
    return cnt


print(dfs(s - 1))

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик