e-olymp 4000. Обход в глубину

Условие:

           Имя входного файла:                «input.txt»
           Имя выходного файла:             стандартный поток вывода
           Ограничение по времени:      1 second
           Ограничение по памяти:       122.17 мегабайт
Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).

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

В первой строке содержится количество вершин графа [latex] n [/latex] и выделенная вершина [latex] s [/latex] [latex](1 ≤ s ≤ n ≤ 100) [/latex]. В следующих [latex] n [/latex] строках записано по [latex] n [/latex] чисел — матрица смежности графа, в которой цифра [latex] «0» [/latex] означает отсутствие ребра между вершинами, а цифра [latex] «1» [/latex] — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

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

Тесты:

Входные данные Выходные данные
1
5 1
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0
3
2
 1 1
 0
 1
3
3 3
0 1 1
1 0 1
1 1 0
 3
4
3 1
0 0 0
0 0 1
1 1 0
1

Решение:

Поскольку нам необходимо найти компоненту связности, запустим из исходной вершины поиск в глубину, запоминая посещенные вершины в массиве [latex] used [/latex]. Те вершины, которые мы посетили — принадлежат той же компоненте связности, что и исходная вершина. Таким образом, подсчитав кол-во посещенных вершин, мы решим задачу.

One thought on “e-olymp 4000. Обход в глубину

Добавить комментарий