Условие
Задача взята с сайта e-olymp.
Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.
Входные данные
В первой строчке находится число [latex]1 \leq N \leq 1000[/latex] В следующих [latex]N[/latex] строчках находится матрица смежности.
Выходные данные
Выведите [latex]N[/latex] чисел – степени всех вершин.
Тесты
Ввод | Вывод |
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 0 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 |
Алгоритм
Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия [latex]N[/latex] раз, для каждой строки матрицы. Храним ответ в переменной counter, изначально [latex]0[/latex]. По очереди считываем все ее элементы и, если текущий элемент равен [latex]1[/latex], то прибавялем степени [latex]2[/latex], если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — [latex]1[/latex]. Затем выводим результат через пробел.
Код
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include <iostream> using namespace std; int main() { ios::sync_with_stdio(false); int n; cin >> n; for (int i = 0; i < n; i++) { int counter = 0, x; for (int j = 0; j < n; j++) { cin >> x; if (x) counter += (i == j ? 2 : 1); } cout << counter << " "; } return 0; } |
Ссылки
Засчитанное решение на e-olymp.
Код для тестирования на Ideone.
Мда, угадал я с задачей. Зачтено.
Может из субботней олимпиады что-то опубликуете?
Например, задачу М?
Спасибо. Еще не решал, попробую, когда дорешивание откроют.
Эту оставлять же?