Traffic lights (Editorial)

The system of intersections and tunnels naturally forms a graph: intersections are vertices, and tunnels are edges. Since the tunnels are bidirectional, the graph is undirected.

The number of traffic lights installed at the $k$-th intersection equals the degree of vertex $k$, that is, the number of tunnels incident to that intersection.

Let us define an array $ton$, where $ton[k]$ represents the number of tunnels adjacent to the $k$-th intersection. Then, for each undirected edge $(a,b)$, increment both $ton[a]$ and $ton[b]$ by one.

Example

The graph shown in the example looks as follows:

Algorithm implementation

Define an array $ton$ to store information about the tunnels.

#define MAX 110
int ton[MAX];

Read the input data. Process each tunnel sequentially, increasing the degrees of the corresponding vertices in the graph.

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

Print the number of traffic lights required at each intersection.

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