Минер

Рассмотрим любой остов графа. Если можно его взорвать, то можно взорвать весь граф, так как остов содержит все вершины. Заметим, что остов можно полностью взорвать, если он не состоит из одной вершины, следующим алгоритмом:

Время работы:

  1. Сортировка: $$$\mathcal{O}(n \log n)$$$ или $$$\mathcal{O}(n)$$$ подсчетом.
  2. Алгоритм: $$$\mathcal{O}(1)$$$ на каждой итерации. Всего итераций $$$\mathcal{O}(n)$$$, поэтому суммарное время работы $$$\mathcal{O}(n)$$$.