Requlyar qraf#5076

Requlyar qraf (Həll təhlili)

Qrafın hər bir təpəsinin dərəcəsini hesablayaq. Əgər bütün təpələrin dərəcələri eynidirsə, onda qraf requlyardır; əks halda — deyil.

Nümunə

Nümunələrdə verilmiş qraflar aşağıdakı görünüşə malikdir:

Birinci qrafın bütün təpələrinin dərəcələri $2$ -yə bərabərdir, buna görə də o requlyardır. İkinci nümunədə təpələrin dərəcələri müxtəlifdir, deməli, bu qraf requlyar deyil.

Alqoritmin realizasiyası

Təpələrin dərəcələrini $d e g$ massivində hesablayacağıq.

#define MAX 110
int deg[MAX];

Giriş məlumatlarını oxuyuruq.

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

Hər bir yönəldilməmiş $(a, b)$ tili üçün $a$ və $b$ təpələrinin dərəcələrini $1$ artırırıq.

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

$d e g$ massivinin bütün qiymətlərinin bərabər olub-olmadığını yoxlayırıq. Əgər bütün qiymətlər üst-üstə düşürsə (yəni bütün təpələrin dərəcələri eynidirsə), onda $f l a g = 0$ flag = 0 olur və qraf requlyardır.

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

$f l a g$ dəyişəninin qiymətindən asılı olaraq cavabı çap edirik.

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