❄Тренировка по теме «Графы»

Соревнование завершилось 04.11.18 в 23:00

A. Обход графа в глубину

Автор задачи: Хаустов Павел
Источник: Летние сборы школьников ТПУ 2012
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Матрицей смежности задан простой невзвешенный граф.

Дан номер некоторой вершины S.

Требуется определить количество вершин, находящихся в одной компоненте связности с S.

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

В первой строке входного файла содержится число N — число вершин в графе (натуральное число не более 100) и, отделенное от него пробелом, число S — номер вершины (от 1 до N), компоненту связности которой необходимо найти.

Далее следует N строк по N чисел (0 обозначает отсутствие ребра, 1 обозначает присутствие ребра), задающих матрицу смежности простого, невзвешенного графа.

Вершины нумерются с единицы.

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

В единственной строке выведите единственное число K — число вершин, которое содержит компонента связности, в которой находится вершина S.

Примеры
Стандартный вводСтандартный вывод
4 1
0 1 0 0
1 0 1 0
0 1 0 0
0 0 0 0
3