e-olymp 5080. Количество висячих вершин 1

Задача

Дан простой неориентированный невзвешенный граф. Подсчитать количество висячих вершин в нем. Вершина называется висячей, если ее степень равна $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$

Код программы

Решение

Введем обозначения: $gr$ – имя массива(матрицы смежности), $n$ – количество вершин, $cnt$ – счётчик.
Просматривая матрицу смежности, подсчитываем количество единиц, т.е количество инцидентных вершин данной вершине. Инцидентные вершины — вершины, которые соединены ребром. Степенью вершины называется количество рёбер, инцидентных этой вершине. Висячей вершиной называют вершину, степень которой равна 1. Соответственно, если в каком-либо ряду в матрице только одна единица, то вершина имеет степень 1 и является висячей.
Сперва предположим, что что граф не имеет висячих вершин, далее введём матрицу смежности, подсчитаем степень вершины и проверим, является ли вершина висячей. В ответе выводим количество висячих вершин в графе.

Ссылки

Условие задачи на e-olymp

Код решения задачи ideone

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *