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

4 thoughts on “e-olymp 5082. Degrees of vertices

  1. Можно ускорить в два раза если читать строку целиком и считать в ней единицы. Тогда решение укладывается в лимит времени.

    Если же аккуратно сделать тоже самое на С++, то можно легко побить все рекорды скорости по этой задаче.

    • Спасибо, так действительно быстрее работает. Подправить пост или оставить все как есть?

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

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