UniLecs #132. Дураки и дороги
UniLecs
Задача: в одной стране есть N городов, и к сожалению, только нектр из них соединены дорогами. Необходимо посчитать кол-во дорог в этой стране.
Входные данные: квадратная матрица N*N с нулями и единицами, и если элемент (i,j) равен 1, то iй и jй города соединены дорогой, если ноль, то нет.
Вывод: кол-во дорог.
Пример:
0 1
1 0
Answer: 1 дорога.
Идея: исходя из условия получаем, что arr[i,j] = arr[j,i] = 1. Поэтому просто проходим по матрице, находим все единицы и делим их кол-во пополам. (Стоит заметить, что мы не делаем проверки исходных данных и считаем, что матрица задана верно, где arr[i,j] == arr[j,i]).
Реализация:
https://gist.github.com/unilecs/41fba3e8a580383364e8475158c3c9d2
Test: