İşıqforlar (Həll təhlili)

Perekrəstklər və tunellər sistemi təbii şəkildə bir qraf təyin edir: perekrəstklər təpələr, tunellər isə tillərdir. Tunellər ikitərəfli olduğundan, qraf istiqamətləndirilməmişdir.

$k$-cı perekrəstdə quraşdırılan svetoforların sayı $k$ təpəsinin dərəcəsinə, yəni bu perekrəstə insident olan tunellərin sayına bərabərdir.

$ton$ massivini təşkil edək, burada $ton[k]$ — $k$-cı perekrəstə bitişik tunellərin sayıdır. Onda hər bir $(a,b)$ istiqamətləndirilməmiş tili üçün $ton[a]$ və $ton[b]$ qiymətlərini bir vahid artırmaq lazımdır.

Nümunə

Nümunədə verilmiş qraf aşağıdakı şəkildədir:

Alqoritmin realizasiyası

Tunellər haqqında məlumatı saxlayacağımız $ton$ massivini elan edək.

#define MAX 110
int ton[MAX];

Giriş məlumatlarını oxuyuruq. Hər bir tuneli ardıcıl olaraq emal edərək, qrafın müvafiq təpələrinin dərəcələrini artırırıq.

scanf("%d %d",&n,&m);
memset(ton,0,sizeof(ton));
for (i = 0; i < m; i++)
{
  scanf("%d %d",&a,&b);
  ton[a]++; ton[b]++;
}

Hər bir perekrəstdə lazım olan svetoforların sayını çap edirik.

for (i = 1; i <= n; i++)
  printf("%d ",ton[i]);
printf("\n");