4764. Степени вершин

Простой неориентированный граф задан матрицей смежности. Найдите степени всех вершин графа.

Вход. В первой строке задано количество вершин графа n (1 ≤ n ≤ 100). Затем идут n строк по n элементов в каждой – описание матрицы смежности.

Выход. Выведите n чисел – степени всех вершин.

Пример входа	Пример выхода
3 0 1 0 1 0 1 0 1 0	1 2 1

РЕШЕНИЕ

графы

Анализ алгоритма

Объявим линейный массив deg. В ячейке deg[i] будем подсчитывать степень вешины i, которая равна количеству единиц в i-ой строке матрицы смежности.

В неориентированном графе каждое ребро встречается дважды (если m – матрица смежности и между ребрами i и j имеется ребро, то m[i][j] = m[j][i] = 1). Для каждого ребра (i, j) будем увеличивать deg[i] на 1 (когда встретится ребро (j, i), то deg[j] увеличится на 1).

Пример

Граф, заданный в примере, имеет вид:

Реализация алгоритма

Объявим массив степеней вершин deg.

#define MAX 101

int deg[MAX];

Читаем количество вершин графа n. Инициализируем массив deg.

scanf("%d",&n);

memset(deg,0,sizeof(deg));

Читаем матрицу смежности.

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

{

Если в графе присутствует ребро (i, j), то есть value = 1, то увеличим deg[i] на единицу.

scanf("%d",&value);

if (value == 1) deg[i]++;

}

Выводим степени вершин графа.

for(i = 0; i < n; i++)

printf("%d\n",deg[i]);

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int deg[] = new int[n];

for(int i = 0; i < n; i++)

for(int j = 0; j < n; j++)

{

int value = con.nextInt();

if (value == 1) deg[i]++;

}

for(int i = 0; i < n; i++)

System.out.println(deg[i]);

con.close();

}

}

Python реализация

Читаем количество вершин графа n.

n = int(input())

Инициализируем матрицу смежности g и массив степеней вершин deg.

g = [[] for _ in range(n)]

deg = [0] * n

Читаем матрицу смежности.

for i in range(n):

g[i] = list(map(int, input().split()))

Вычисляем степени вершин графа. Степень вершины i равна сумме чисел i-ой строки матрицы смежности g.

for i in range(n):

deg[i] = sum(g[i])

Выводим степени вершин графа.

for i in range(n):

print(deg[i])