Città e strade (Editoriale)

Sia $g$ la matrice di adiacenza del grafo. Poiché il grafo è non orientato, nel caso in cui esista uno spigolo tra i vertici $i$ e $j$ valgono le uguaglianze:

Il numero di spigoli nel grafo è uguale al numero di uno nella matrice di adiacenza, diviso per $2$.

Esempio

Il grafo riportato nell'esempio ha la forma:

Il numero di strade sul pianeta è pari a $3$.

Implementazione dell'algoritmo

Leggiamo il valore di input $n$.

scanf("%d",\&n);

Leggiamo la matrice di adiacenza. Calcoliamo la somma dei numeri $res$ in essa. Poiché il grafo è non orientato, $res$ è uguale al doppio del numero di spigoli.

res = 0;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
{
  scanf("%d",\&val);
  res += val;
}

Calcoliamo e stampiamo il numero di spigoli.

res /= 2;
printf("%d\n",res);

Implementazione in Java

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();
  }
}

Implementazione in Python — al volo

Leggiamo il valore di input $n$.

n = int(input())

Calcoliamo la somma dei numeri nella matrice di adiacenza nella variabile $res$.

res = 0

Leggiamo la matrice di adiacenza riga per riga. Per ogni riga calcoliamo la somma dei numeri in essa contenuti. Poi aggiungiamo questa somma al valore $res$.

for _ in range(n):
  res += sum(map(int, input().split()))

Poiché il grafo è non orientato, la somma $res$ è uguale al doppio del numero di spigoli. Dividiamo $res$ per $2$ e stampiamo la risposta.

res //= 2
print(res)

Implementazione in Python — matrice di adiacenza

Leggiamo i dati di input.

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

Calcoliamo la somma dei numeri $s$ nella matrice di adiacenza. Poiché il grafo è non orientato, $s$ è uguale al doppio del numero di spigoli.

s = 0
for row in g:
  s += sum(row)

Stampiamo il numero di spigoli.

print(s // 2)