Cijanobakterije
레이팅 미적용의견: 0
Young microbiologist Maja is making a microscopic Christmas tree out of a species of
cyanobacteria called Stigonema arboreus. This species is known for its colonies made
from individual cells which link together, forming a tree graph. More precisely, for each
pair of cyanobacteria in the colony, there is a unique path through the colony from one
cyanobacterium to the other.
Maja wants her Christmas tree colony to contain a chain of cyanobacteria that is as
long as possible. A chain is determined by a sequence of cyanobacteria, where each
cyanobacterium appears at most once, and every pair of adjacent cyanobacteria are
directly linked together. Because none of the colonies she currently has is long enough,
Maja will have to connect some of the colonies together. She does this by repeatedly choosing two
cyanobacteria from different colonies, bringing them close to each other, and joining them with superglue.
Since the bacteria are sensitive to cycles, Maja has to be careful not to join two bacteria from the same
colony at any time. Using a series of such gluing procedures, Maja wants to obtain a colony which contains
the longest possible chain.
Maja is tired from using her microscope, and there a lot of cyanobacteria. Help Maja determine the length
of the longest chain of cyanobacteria she could obtain by connecting the colonies. The length of a chain is
determined by the number of cyanobacteria from which it is formed.
Subtask 1 (15 points): \(m = n - 1\)
Subtask 2 (6 points): \(b_{i} = a_{i} + 1\) for each \(i = 1\), . . . , m
Subtask 3 (6 points): \(1 \le a\)\(i \le 2\) for each \(i = 1\), . . . , m
Subtask 4 (15 points): \(1 \le n \le 1000\)
Subtask 5 (28 points): No additional constrains.
The first line contains positive integers \(n\) and \(m\) (\(1 \le n \le 100\,000\), \(0 \le m < n\)), the number of
cyanobacteria and the number of direct connections between them.
The following \(m\) lines contain a pair of positive integers \(a@@RISE_MATH_BLOCK_0@@i\) (\(1 \le a@@RISE_MATH_BLOCK_1@@i\) and \(b\)\(i\) are directly linked. No bacterium is directly linked to itself, and no connection will be
listed more than once.
The connections are such that the bacteria form some colonies, each of which is a tree.
In the only line print the largest possible length of a chain in the final colony.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | \(m = n - 1\) |
2 | 6점 | \(b_{i} = a_{i} + 1\) for each \(i = 1\), . . . , m |
3 | 6점 | \(1 \le a\)\(i \le 2\) for each \(i = 1\), . . . , m |
4 | 15점 | \(1 \le n \le 1000\) |
5 | 28점 | No additional constrains. |
100 01008 6
1 2
1 3
1 4
5 6
5 7
5 866 5
1 2
2 3
3 4
4 6
4 55Clarification of the second example:
In the second example there are two colonies of cyanobacteria. In the first colony, all cyanobacteria are
directly connected to cyanobacterium 1, and in the second with cyanobacterium 5. If any two cyanobacteria
except 1 and except 5 are connected, the resulting colony will contain the longest possible chain. Eg. if 2
and 6 are connected, one such chain will be 3 - 1 - 2 - 6 - 5 - 7 which has length 6.
평가 및 의견
Cijanobakterije
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Cijanobakterije