Задача
Найдите размер компоненты связности, содержащей заданную вершину в неориентированном графе.
Входные данные
В первой строке записаны числа $N$ и $S$ ($1 \leqslant N \leqslant 100$, $1 \leqslant S \leqslant N$) — количество вершин и номер стартовой вершины. Далее следует матрица смежности графа: $N$ строк по $N$ чисел, где $0$ означает отсутствие ребра, а $1$ — его наличие. На главной диагонали всегда стоят нули.
Выходные данные
Выведите одно число — количество вершин в компоненте связности, содержащей вершину $S$.
Пример
стандартный ввод стандартный вывод
3 1 3
0 1 1
1 0 0
1 0 0
Ограничения
- Время: 1 секунда
- Память: 256 мегабайт
Редакционный разбор
Так как граф задан матрицей смежности, проще всего выполнять обход, перебирая всю строку матрицы для текущей вершины. Стартуем DFS/BFS из вершины $S$, отмечаем посещённые вершины и считаем их количество.
Псевдокод DFS:
```cpp
vector used(n);
function<void(int)> dfs = [&](int v) {
used[v] = 1;
for (int u = 0; u < n; ++u) if (g[v][u] && !used[u]) {
dfs(u);
}
};
dfs(S-1);
int ans = accumulate(used.begin(), used.end(), 0);
```
Матрица $100 \times 100$ легко помещается в память. Сложность $O(N^2)$ за счёт перебора всех строк.
</details>
### Mentioned by
- [DFS1 — параллель B'](/dsa-notes/bp2025/contests/dfs1/){: .dsa-mention } — F: 6. Обход графа
- [Каталог задач](/dsa-notes/problems/){: .dsa-mention } — F: 6. Обход графа
