Asma təpələrin sayı 1 (Həll təhlili)

Hər bir $i$ təpəsi üçün onunla qonşu olan təpələrin sayını hesablayaq. Əgər bu say $1$-ə bərabərdirsə, onda $i$ təpəsi asma təpədir.

Nümunə

Misallarda verilən qraflar aşağıdakı görünüşə malikdir:

Birinci misalda qraf $1$ dərəcəli iki təpə saxlayır. Deməli, orada iki asma təpə var.

İkinci misalda $1$ dərəcəli (asma) təpələr yoxdur.

Alqoritmin realizasiyası

$m$ massivini elan edək, burada $m[i]$ — $i$ təpəsi ilə qonşu olan təpələrin sayıdır.

#define MAX 1010
int m[MAX];

Qonşuluq (istiqamətlənməmiş qraf) matrisini oxuyuruq. Hər bir $(i,j)$ tili üçün $m[i]$-nin qiymətini $1$ artırırıq ($m[j]$-nin qiyməti isə $(j,i)$ tili nəzərdən keçirildikdə artacaq).

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]++;
}

Əgər m[i] = 1-dirsə, onda $i$ təpəsi düz bir təpə ilə birləşib, yəni asma təpədir. Bu cür təpələrin sayını hesablayır və nəticəni $res$ dəyişənində saxlayırıq.

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

Cavabı çap edirik.

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