Semafori (Editoriale)

Il sistema di incroci e tunnel definisce naturalmente un grafo: gli incroci sono i vertici, mentre i tunnel sono gli archi. Poiché i tunnel sono bidirezionali, il grafo è non orientato.

Il numero di semafori da installare al $k$-esimo incrocio è pari al grado del vertice $k$, ovvero al numero di tunnel incidenti a tale incrocio.

Creiamo un array $ton$, dove $ton[k]$ — è il numero di tunnel adiacenti al $k$-esimo incrocio. Allora, per ogni arco non orientato $(a,b)$, è necessario incrementare di uno i valori $ton[a]$ e $ton[b]$.

Esempio

Il grafo riportato nell'esempio ha il seguente aspetto:

Implementazione dell'algoritmo

Dichiariamo un array $ton$, in cui memorizzeremo le informazioni sui tunnel.

#define MAX 110
int ton[MAX];

Leggiamo i dati in input. Elaboriamo in sequenza ciascun tunnel, incrementando i gradi dei vertici corrispondenti del grafo.

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

Stampiamo il numero di semafori necessari per ciascun incrocio.

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