Cities and roads (Editorial)

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:

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 implementation

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 implementation

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 implementation — 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 implementation — 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)