992. Cities and roads

In the galaxy of “Milky Way” on the planet “Neptune” there are n cities, some of them are connected by roads. Emperor “Maximus” of Galaxy “Milky Way” has decided to make an inventory of roads on the planet “Neptune”. But as it turned out he was not 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 of which is one or zero. Moreover, if the position (i, j) of square matrix is one, then the i-th and j-th city are connected by road, and if zero, it is not connected.

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

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 the vertices i and j, we have the equalities:

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

The number of edges in the graph equals to 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, the sum 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 calculated in the variable res.

res = 0

Read the adjacency matrix row by row. For each line, compute the sum of the numbers in it. Then add this sum to the variable 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 numbers s in the adjacency matrix. Since the graph is undirected, the 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)