993. Traffic lights
There are m tunnels and n intersections in the dungeon. Each
tunnel connects two intersections. The Rat King decided to install a traffic
light in each tunnel before each intersection.
Write a program
that determines how many traffic lights need to be installed at each
intersection. The intersections are numbered from 1 to n.
Input. The first line contains two integers n and m (0 < n ≤ 100, 0 ≤ m ≤ n · (n – 1) / 2). Each of the next m lines contains two integers i and j (1 ≤ i, j
≤ n), indicating that intersections i and j are connected by a tunnel.
Output. Print n integers: the k-th integer is the number
of traffic lights that need to be installed at the k-th intersection.
It is guaranteed
that there is at most one tunnel between any two intersections, and there are
no tunnels connecting an intersection to itself.
|
Sample
input |
Sample
output |
|
7 10 5 1 3 2 7 1 5 2 7 4 6 5 6 4 7 5 2 1 5 3 |
3 3 2 2 5 2
3 |
SOLUTION
graphs
Algorithm analysis
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");