Точки и линии

В задаче требовалось вывести «Yes», если возможно построить неориентированный граф из N вершин и M ребер, так, чтобы он был несвязным. Разберем, какое максимальное количество ребер может быть в несвязном графе из N вершин.

Пусть G – это граф, имеющий N вершин, K компонент связности и максимально возможное количество ребер M. Покажем, что M =(N−K)•(N−K+1)/2.

Легко понять, что каждая компонента графа G является полным графом. Пусть ni количество вершин в компоненте с номером i. Без ограничения общности можно полагать, что n₁ ≥ n₂ ≥ ... ≥ n_k. Докажем, что n₂ = n₃ = ... = n_k = 1. Предположим, что n₂ > 1, тогда если мы отцепим от компоненты 2 вершину u, то потеряем n₂−1 ребро. Прицепим u к первой компоненте, таким образом, получая n₁ новых ребер. Так как n₁ > n₂−1, то получаем, что если n₂ > 1, то M не максимально, что противоречит выбору G. Таким образом, n₂ = n₃ = ... = n_k = 1.

Теперь из формулы максимального количества ребер для k компонент легко установить, что выгоднее всего брать k = 2. Таким образом, получаем решение:

  read(n,m)
  if((n-1)∙(n−2) >= 2*m) write('Yes') else write('No')

Разбор: Александр Торопов.

[Обсуждение] [Все попытки] [Задача]