e-olymp 5082. Degrees of vertices

Задача взята с сайта e-olymp.com.

Условие

Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.

Входные данные

В первой строчке находится число 1 \leq N \leq 1000. В следующих N строчках находится матрица смежности.

Выходные данные

Выведите N чисел – степени всех вершин.

Тесты :

Ввод Вывод
2
0 1
1 0
1 1
 3
0 1 0
1 0 1
0 1 0
 1 2 1
 3
0 1 0
1 1 1
0 1 0
1 4 1
 5
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
1 0 0 0 0
1 1 1 1 1
 6 1 6 1 6
 5
0 0 1 0 0
0 1 0 1 0
0 1 1 1 0
0 1 0 1 0
1 0 0 0 1
 1 3 4 3 3
 5
0 1 1 1 1
1 0 0 0 0
0 1 1 1 0
0 0 0 0 1
1 1 1 1 0
 4 1 4 1 4
 5
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
 3 3 2 1 1

Код на Java:

Алгоритм:

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия N раз, для каждой строки матрицы. Храним ответ в переменной counter, изначально 0. По очереди считываем все ее элементы и, если текущий элемент равен 1, то прибавляем степени 2, если элемент принадлежит главной диагонали (так как тогда это ребро является петлей, а при подсчете степени ребро-петля учитывается дважды), иначе прибавляем 1. Формируем строку-результат и выводим её.

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com