Задача
Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна $1.$
Входные данные
В первой строке находится число $n$ $\left ( 1 \leq n \leq 1000 \right ).$ В следующих $n$ строках находится матрица смежности.
Выходные данные
Выведите количество висячих вершин в графе.
Тесты
| Входные данные | Выходные данные |
| $2 \\ 0 \ 1 \\ 1 \ 0$ | $2$ |
| $3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 1 \ 0$ | $0$ |
| $4 \\ 1 \ 0 \ 0 \ 0 \\ 0 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1$ | $4$ |
| $3 \\ 0 \ 1 \ 1 \\ 1 \ 0 \ 1 \\ 1 \ 0 \ 0$ | $1$ |
Код программы
|
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 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { int [][] gr = new int [1001][1001]; Scanner in = new Scanner(System.in); int n = in.nextInt(); int ans = 0; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { gr[i][j] = in.nextInt(); } } for (int i=0; i<n; i++) { int cnt = 0; for (int j=0; j<n; j++) { if (gr[i][j] == 1) cnt++; } if (cnt==1) ans++; } System.out.println(ans); } } |
Решение
Введем обозначения: $gr$ – имя массива(матрицы смежности), $n$ – количество вершин, $cnt$ – счётчик.
Просматривая матрицу смежности, подсчитываем количество единиц, т.е количество инцидентных вершин данной вершине. Инцидентные вершины — вершины, которые соединены ребром. Степенью вершины называется количество рёбер, инцидентных этой вершине. Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице только одна единица, то вершина имеет степень 1 и является висячей.
Сперва предположим, что что граф не имеет висячих вершин, далее введём матрицу смежности, подсчитаем степень вершины и проверим, является ли вершина висячей. В ответе выводим количество висячих вершин в графе.
Ссылки
Условие задачи на e-olymp
Код решения задачи ideone