Задача
Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).
Входные данные
В первой строке содержится количество вершин графа $n$ и выделенная вершина $s$ $\left (1 \leq s \leq n \leq 100 \right).$ В следующих n строках записано по n чисел — матрица смежности графа, в котрой цифра «$0$» означает отсутствие ребра между вершинами, а цифра «$1$» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.
Выходные данные
Выведите искомое количество вершин.
Тесты
Входные данные | Выходные данные |
3 1 0 0 1 0 0 0 1 0 0 |
2 |
4 2 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 |
4 |
6 2 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 |
3 |
4 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
1 |
5 3 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 |
5 |
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <cmath> #include <iomanip> #include <vector> using namespace std; void dfs(int cur, vector<vector<int>> & adj, vector<bool> & was, int & count){ if(!was[cur]){ was[cur] = true; count++; for(int i = 0; i < adj[cur].size(); i++){ dfs(adj[cur][i], adj, was, count); } } } int getCount(int start, vector<vector<int>> & adj){ vector<bool> was(adj.size(), false); int count = 0; dfs(start, adj, was, count); return count; } int main() { int n; cin >> n; int start; cin >> start; start--; vector<vector<int>> adj(n, vector<int>()); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ int temp; cin >> temp; if(temp == 1){ adj[i].push_back(j); } } } cout << getCount(start, adj); return 0; } |
Решение задачи
Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа $c$ будет искомым числом.
Ссылки
Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone