Міста та дороги (Розбір)

Нехай $g$ — матриця суміжності графа. Оскільки граф неорієнтований, то у випадку наявності ребра між вершинами $i$ та $j$ маємо рівності:

Кількість ребер у графі дорівнює кількості одиниць у матриці суміжності, поділеній на $2$.

Приклад

Граф, наведений у прикладі, має вигляд:

Кількість доріг на планеті дорівнює $3$.

Реалізація алгоритму

Читаємо вхідне значення $n$.

scanf("%d",&n);

Читаємо матрицю суміжності. Обчислюємо суму чисел $res$ у ній. Оскільки граф неорієнтований, то $res$ дорівнює подвоєній кількості ребер.

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

Обчислюємо та виводимо кількість ребер.

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

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

Python реалізація — на льоту

Читаємо вхідне значення $n$.

n = int(input())

Суму чисел у матриці суміжності обчислюємо у змінній $res$.

res = 0

Читаємо матрицю суміжності рядок за рядком. Для кожного рядка обчислюємо суму чисел у ньому. Потім додаємо цю суму до значення $res$.

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

Оскільки граф неорієнтований, то сума $res$ дорівнює подвоєній кількості ребер. Ділимо $res$ на $2$ та виводимо відповідь.

res //= 2
print(res)

Python реалізація — матриця суміжності

Читаємо вхідні дані.

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

Обчислюємо суму чисел $s$ у матриці суміжності. Оскільки граф неорієнтований, то $s$ дорівнює подвоєній кількості ребер.

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

Виводимо кількість ребер.

print(s // 2)