Задача
Дан неориентированный невзвешенный граф, в котором выделена вершина. Вам необходимо найти количество вершин, лежащих с ней в одной компоненте связности (включая саму вершину).
Входные данные
В первой строке содержится количество вершин графа $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 |
import java.util.ArrayList; import java.util.Scanner; public class Main { private static int count = 0; private static void dfs(ArrayList<Integer>[] adj, boolean[] was, int v) { count++; for (int e: adj[v]) { if (!was[e]) { was[e] = true; dfs(adj, was, e); } } } private static void dfs(ArrayList<Integer>[] adj, int v) { boolean[] was = new boolean[adj.length]; was[v] = true; dfs(adj, was, v); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int v = scanner.nextInt() - 1; ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); for (int j = 0; j < n; j++) { int d = scanner.nextInt(); if (d == 1) { adj[i].add(j); } } } dfs(adj, v); System.out.println(count); } } |
Решение задачи
Для хранения графа воспользуемся списками смежности. Реализуем стандартный поиск в глубину. Пусть $c$ количество вершин в компоненте графа. Изначально $c = 0.$ При посещении очередной, не посещенной ранее вершины, значение $c$ увеличивается на один. Таким образом, при полном обходе компоненты графа, $c$ будет искомым числом.
Ссылки
Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone