Grafo regolare#5076

Grafo regolare (Editoriale)

Calcoliamo il grado di ogni vertice del grafo. Se i gradi di tutti i vertici sono uguali, allora il grafo è regolare; in caso contrario — non lo è.

Esempio

I grafi riportati negli esempi hanno il seguente aspetto:

I gradi di tutti i vertici del primo grafo sono uguali a $2$ , pertanto esso è regolare. Nel secondo esempio i vertici hanno gradi diversi, di conseguenza questo grafo non è regolare.

Implementazione dell'algoritmo

Calcoleremo i gradi dei vertici nell'array $d e g$ .

#define MAX 110
int deg[MAX];

Leggiamo i dati di input.

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

Per ogni arco non orientato $(a, b)$ incrementiamo di $1$ i gradi dei vertici $a$ e $b$ .

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

Verifichiamo se tutti i valori dell'array $d e g$ sono uguali. Se tutti i valori coincidono (cioè i gradi di tutti i vertici sono uguali), allora $f l a g = 0$ flag = 0, e il grafo è regolare.

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

A seconda del valore della variabile $f l a g$ stampiamo la risposta.

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