992. Cities and roads

In the “Milky Way” galaxy, on the planet “Neptune” there are n cities, some of which are connected by roads. Emperor “Maximus” of the “Milky Way” galaxy has decided to make an inventory of the roads on “Neptune”. However, as it turns out, he is not very good at math, so he asks you to count the number of roads.

Input. The first line contains the number n (0 ≤ n ≤ 100). Each of the next n lines contains n numbers, each either one or zero. If the position (i, j) in the square matrix is one, then the i-th and j-th cities are connected by a road; if it is zero, they are not connected.

Output . Print the number of roads on the planet “Neptune”.

Sample input	Sample output
5 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0	3

SOLUTION

graphs

Algorithm analysis

Let g be the adjacency matrix of the graph. Since the graph is undirected, if there is an edge between vertices i and j, the following equality holds:

g[i][j] = g[j][i] = 1

The number of edges in the graph equals the number of ones in the adjacency matrix divided by 2.

Example

The graph given in the example, has the form:

The number of roads on the planet is 3.

Algorithm realization

Read the input value of n.

scanf("%d",&n);

Read the adjacency matrix. Compute the sum of the numbers res in it. Since the graph is undirected, res is equal to twice the number of edges.

res = 0;

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

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

{

scanf("%d",&val);

res += val;

}

Compute and print the number of edges.

res /= 2;

printf("%d\n",res);

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int res = 0;

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

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

res += con.nextInt();

res /= 2;

System.out.println(res);

con.close();

}

}

Python realization – on fly

Read the input value of n.

n = int(input())

The sum of the numbers in the adjacency matrix is stored in the variable res.

res = 0

Read the adjacency matrix row by row. For each row, compute the sum of the numbers in it. Then add this sum to res.

for _ in range(n):

res += sum(map(int, input().split()))

Since the graph is undirected, the sum res is equal to twice the number of edges. Divide res by 2 and print the answer.

res //= 2

print(res)

Python realization – adjacency matrix

Read the input data.

n = int(input())

g = [[int(j) for j in input().split()] for i in range(n)]

Compute the sum of the numbers s in the adjacency matrix. Since the graph is undirected, this sum s is equal to twice the number of edges.

s = 0

for row in g:

s += sum(row)

Print the number of edges.

print(s // 2)