Задача
Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.
Входные данные
В первой строчке находится число $N (1 ≤ N ≤ 1000)$. В следующих $N$ строчках находится матрица смежности.
Выходные данные
Выведите $N$ чисел – степени всех вершин.
Тесты
| Входные данные | Выходные данные |
| 2 0 1 1 0 |
1 1 |
| 3 0 1 0 1 0 1 0 1 0 |
1 2 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 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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
import java.util.*; import java.lang.*; import java.io.*; class Main { static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(System.out); static int nextInt() throws IOException { in.nextToken(); return (int)in.nval; } public static void main (String[] args) throws java.lang.Exception { int n = nextInt(); for (int i = 0; i < n; i++) { int counter = 0, x; for (int j = 0; j < n; j++) { x = nextInt(); if (x > 0) counter += (i == j ? 2 : 1); } out.print (counter + " "); out.flush(); } } } |
Решение задачи
Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия $N$ раз, для каждой строки матрицы. Храним ответ в переменной counter , изначально $0$. По очереди считываем все ее элементы и, если текущий элемент равен $1$, то прибавялем степени $2$, если элемент принадлежит главной диагонали (т.к. тогда это петля, а при подсчете степени ребро-петля учитывается дважды), иначе — $2$. Затем выводим результат через пробел.
Ссылки
Условие задачи на e-olymp.com
Решение задачи на ideone.com