Mənbələrin sayılması (Həll təhlili)

Məsələni həll etmək üçün qrafın qonşuluq siyahısından qonşuluq matrisinə keçmək əlverişlidir.

n \times n ölçülü qonşuluq matrisi qurulur, burada a_{ij} = 1 elementi, əgər $i$ təpəsindən $j$ təpəsinə yönləndirilmiş qırağ mövcuddursa, əks halda isə $0$ olur.

Sonra hər bir $j$ təpəsi üçün ona daxil olan qırağların sayını hesablayırıq. Bunu qonşuluq matrisinin $j$-ci sütununun elementlərini toplamaqla etmək olar.

Təpə o zaman və yalnız o zaman mənbə (istok) hesab olunur ki, ona heç bir qırağ daxil olmasın, yəni müvafiq sütunun elementlərinin cəmi $0$-a bərabər olsun.

Beləliklə, cavab daxil olan qırağların sayı sıfır olan təpələrin sayıdır.

Nümunə

Qraf bir mənbə — $4$ təpəsini ehtiva edir, çünki ona heç bir qırağ daxil olmur.

Alqoritmin realizasiyası

Qonşuluq matrisini və $in$ massivini elan edirik, burada $in[i]$ $i$ təpəsinə daxil olan qırağların sayını saxlayır.

#define MAX 101
int g[MAX][MAX], in[MAX];

Giriş məlumatlarını oxuyuruq. Verilmiş qonşuluq siyahısına əsasən qonşuluq matrisini qururuq.

scanf("%d", \u0026n);
for (i = 1; i \u003c= n; i++)
{

Hər bir $i$ təpəsi üçün əvvəlcə ondan çıxan qırağların sayı $k$-nı oxuyuruq.

  scanf("%d", \u0026k);
  for (j = 0; j \u003c k; j++)
  {

Hər bir $(i,x)$ qırağı üçün g[i][x] = 1 təyin edirik.

    scanf("%d", \u0026x);
    g[i][x] = 1;
  }
}

Qrafın bütün təpə cütlərini nəzərdən keçiririk. Hər bir $(i,j)$ qırağı üçün $in[j]$ dəyərini $1$ vahid artırırıq, çünki $(i,j)$ qırağı $j$ təpəsinə daxil olur.

for (i = 1; i \u003c= n; i++)
for (j = 1; j \u003c= n; j++)
  if (g[i][j] == 1) in[j]++;

Mənbə-təpələrin sayını hesablayırıq — yəni heç bir qırağın daxil olmadığı təpələrin sayını (bunlar üçün in[i] = 0).

int source = 0;
for (i = 1; i \u003c= n; i++)
  if (in[i] == 0) source++;

Cavabı çap edirik.

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