- 43
Statement
Goal
Given a population size and a network of connections between its members, determine the breakdown of cluster sizes of the population.Imagine that each member of a population is one person. Now consider that one member of the population becomes "infected" by a virus. Provided a set of connections (i.e. "member A is linked to member B"), the subset of members of the population infected by the virus can be simulated (we will assume that transmission is guaranteed to occur between linked members). This subset is effectively like an "outbreak" of a virus.
Your job is to assess these subsets, or clusters and provide the breakdown of the distribution of cluster sizes in the given population.
NOTE: All links are two-way (reciprocal), there are no one-way links.
Given a population size N, with members indexed from
Input:
Line 1: A number, N, of members of the population
Line 2: A number, L, of links within the population
Next L lines: Two space-separated integers representing the indexes of two linked members of the population
Output: "cluster size" and "cluster count" for each cluster, separated by a space; in descending order of size.
Line 1: Two space-separated integers representing the size and frequency of the largest sized cluster.
Line 2: Two space-separated integers representing the size and frequency of the 2-nd largest sized cluster
... and so on:
Last Line: Two space-separated integers representing the size and frequency of the smallest sized cluster
Constraints:
Every member of the population belongs to a cluster even if its size is of 1 (a cluster with only one member).
Input
Line 1 : : the number n_people of elements in the structure
Line 2 : : the number n_links of existing relations between elements in the structure
n_links next lines : two integers i and j for two elements linked
Line 2 : : the number n_links of existing relations between elements in the structure
n_links next lines : two integers i and j for two elements linked
Output
The distribution of clusters in descending order by size of cluster. Each lines containing two integers, "cluster size" and "cluster count" for this cluster size, separated by a space.
Line 1 : the size of the biggest clusters space the number of clusters of this size
...
Line n : the size of the smallest clusters space the number of clusters of this size
Line 1 : the size of the biggest clusters space the number of clusters of this size
...
Line n : the size of the smallest clusters space the number of clusters of this size
Constraints
Number of people 5 <= n_people <= 500
Number of links n_links <800
Number of links n_links <
Example
Input
5 2 4 0 0 2
Output
3 1 1 2
A higher resolution is required to access the IDE