Кількість висячих вершин 1 (Розбір)

Для кожної вершини $i$ підрахуємо кількість вершин, суміжних з нею. Якщо це число дорівнює $1$, то вершина $i$ є висячою.

Приклад

Графи, наведені у прикладах, мають наступний вигляд:

У першому прикладі граф містить дві вершини степеня $1$. Отже, у ньому дві висячі вершини.

У другому прикладі вершин степеня $1$ (висячих) немає.

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

Оголосимо масив $m$, де $m[i]$ — кількість вершин, суміжних з вершиною $i$.

#define MAX 1010
int m[MAX];

Читаємо матрицю суміжності неорієнтованого графа. Для кожного ребра $(i,j)$ збільшуємо значення $m[i]$ на $1$ (значення $m[j]$ збільшиться на $1$, коли розглядатиметься ребро $(j,i)$).

scanf("%d",&n);
memset(m,0,sizeof(m));
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
  scanf("%d",&val);
  if (val) m[i]++;
}

Якщо m[i] = 1, то вершина $i$ з'єднана рівно з однією вершиною, тобто є висячою. Підраховуємо кількість таких вершин і зберігаємо результат у змінній $res$.

res = 0;
for (i = 0; i < n; i++)
  if (m[i] == 1) res++;

Виводимо відповідь.

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