Задача
Простой неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.
Входные данные
В первой строке задано количество вершин графа [latex]n (1 ≤ n ≤ 100)[/latex]. Затем идут [latex]n[/latex] строк по [latex]n[/latex] элементов в каждой — описание матрицы смежности.
Выходные данные
Выведите [latex]n[/latex] чисел — степени всех вершин.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 0 1 0 1 0 1 0 1 0 |
1 2 3 |
| 2 | 4 0 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 |
2 2 1 2 |
| 3 | 4 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 |
3 3 3 3 |
| 4 | 5 0 1 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 0 |
3 3 3 3 4 |
5 | 5 0 1 0 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 0 |
2 4 3 3 4 |
Код задачи
|
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 27 28 29 30 31 |
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); //массив, в котором содержатся степени вершин int deg[] = new int[n]; //Чтение матрицы смежности //и если есть ребро, то увеличиваем степень на 1 for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { int value = in.nextInt(); if (value == 1) { deg[i]++; } } } //вывод результата for(int i = 0; i < n; i++) { System.out.println(deg[i]); } } } |
Решение
В ячейке [latex]deg[i][/latex] будем подсчитывать степень вершины [latex]i[/latex], которая равна количеству единиц в i-ой строки матрицы смежности.
Для неориентированного графа степень вершины — это количество всех инцидентных ей ребер.
Граф [latex]G=(V,U)[/latex] может быть задан матрицей смежности. Это квадратная матрица размерности [latex]n\times n[/latex], где [latex]n=\left |V \right | [/latex]. Матрица смежности неориентированного графа симметрична. Элементы матрицы смежности определяются следующим образом.
1- если [latex]i[/latex]-тая и [latex]j[/latex]-тая вершины графа смежны
0- иначе
[latex] a_{ij}=\left\{\begin{matrix}
1\\
0
\end{matrix}\right.\\[/latex]
Ссылки
Задача на e-olymp
Код задачи на ideone