Регулярний граф (Розбір)

Обчислимо степінь кожної вершини графа. Якщо степені всіх вершин однакові, то граф є регулярним; в іншому випадку — ні.

Приклад

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

Степені всіх вершин першого графа дорівнюють $2$, тому він є регулярним. У другому прикладі вершини мають різні степені, отже, цей граф не є регулярним.

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

Степені вершин будемо підраховувати в масиві $deg$.

#define MAX 110
int deg[MAX];

Зчитуємо вхідні дані.

scanf("%d %d",&n,&m);
memset(deg,0,sizeof(deg));
for(i = 0; i < m; i++)
{

Для кожного неорієнтованого ребра $(a,b)$ збільшуємо на $1$ степені вершин $a$ і $b$.

  scanf("%d %d",&a,&b);
  deg[a]++; deg[b]++;
}

Перевіряємо, чи рівні всі значення масиву $deg$. Якщо всі значення збігаються (тобто степені всіх вершин однакові), то flag = 0, і граф є регулярним.

flag = 0;
for(i = 1; i < n; i++)
  if (deg[i] != deg[i+1]) flag = 1;

Залежно від значення змінної $flag$ виводимо відповідь.

if (flag == 0) printf("YES\n");
else printf("NO\n");