4764. Degrees of vertices

A simple undirected graph is given by its adjacency matrix. Find the degrees of all vertices of the graph.

Input. The first line contains the number of vertices n (1 ≤ n ≤ 100). Then follow n lines, each containing n elements describing the adjacency matrix of the graph.

Output. Print n numbers – the degrees of all vertices of the graph.

Sample input

Sample output

0 1 0

1 0 1

0 1 0

SOLUTION

graphs

Algorithm analysis

Let’s declare a linear array deg. In the cell deg[i] we’ll store the degree of vertex i, which is equal to the number of ones in the i- th row of the adjacency matrix.

In an undirected graph, each edge is counted twice: if m is the adjacency matrix and there is an edge between vertices i and j, then m[i][j] = m[j][i] = 1). For each edge (i, j) we increment deg[i] by 1 (when the edge (j, i) is encountered, deg[j] will be incremented by 1).

Example

The graph given in the example looks as follows:

Algorithm implementation

Let’s declare an array deg to store the degrees of the vertices.

#define MAX 101

int deg[MAX];

Read the number of vertices in the graph n. Initialize the deg array.

scanf("%d",&n);

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

Read the adjacency matrix.

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

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

{

If there is an edge between vertices i and j in the graph (the value value is 1), increment deg[i] by one.

scanf("%d",&value);

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

}

Print the degrees of all the vertices in the graph.

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

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

Java implementation

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 implementation

Read the number of vertices in the graph n.

n = int(input())

Initialize the adjacency matrix g and the list of vertex degrees deg.

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

deg = [0] * n

Read the adjacency matrix.

for i in range(n):

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

Compute the degrees of the graph’s vertices. The degree of vertex i is equal to the sum of the elements in the i-th row of the adjacency matrix g.