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])