UniLecs #166. Основы графов - 2

Задача: дана матрица смежности простого неориентированного графа. Необходимо определить степени всех вершин графа.

Входные данные: arr - матрица смежности, квадратная матрица N*N, состоящая из нулей и единиц, где N от 1 до 10^6.

Вывод: вывести N чисел - степени каждой из вершин.

Пример:

1. [ { 0, 1, 1 },

   { 1, 0, 1 },

   { 1, 1, 0 } ]

Answer = 2, 2, 2

2. [ { 0, 1, 0 },

   { 1, 0, 1 },

   { 0, 1, 0 } ]

Answer = 1, 2, 1

Идея: нужно просто вспомнить теорию графов, а именно определение матрицы смежности и простого неориентированного графа.

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

Так как по условию задачи нам уже дана матрица смежности простого неориентированного графа, то валидацию матрицы мы делать не будем.

Поэтому нам нужно только посчитать количество единиц для каждой строки, это и будет степенью i-й вершины.

Реализация:

https://gist.github.com/unilecs/a9b0104836dcd01b30f705ee4a95dc40

Play-test: https://dotnetfiddle.net/JoXoYR