Світлофори (Розбір)

Система перехресть та тунелів природним чином задає граф: перехрестя є вершинами, а тунелі — ребрами. Оскільки тунелі двонапрямлені, граф є неорієнтованим.

Кількість світлофорів, що встановлюються на $k$-му перехресті, дорівнює степеню вершини $k$, тобто числу тунелів, інцидентних цьому перехрестю.

Заведемо масив $ton$, де $ton[k]$ — кількість тунелів, що прилягають до $k$-го перехрестя. Тоді для кожного неорієнтованого ребра $(a,b)$ необхідно збільшити значення $ton[a]$ та $ton[b]$ на одиницю.

Приклад

Граф, наведений у прикладі, має наступний вигляд:

Реалізація алгоритму

Оголосимо масив $ton$, в якому зберігатимемо інформацію про тунелі.

#define MAX 110
int ton[MAX];

Зчитуємо вхідні дані. Послідовно обробляємо кожен тунель, збільшуючи степені відповідних вершин графа.

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

Виводимо кількість світлофорів, необхідних на кожному перехресті.

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