Degrees of vertices (Editorial)

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$.

for i in range(n):
  deg[i] = sum(g[i])

Print the degrees of all the vertices in the graph.

for i in range(n):
  print(deg[i])