Рассмотрим любой остов графа. Если можно его взорвать, то можно взорвать весь граф, так как остов содержит все вершины. Заметим, что остов можно полностью взорвать, если он не состоит из одной вершины, следующим алгоритмом:
- Подвесим остов за любую вершину.
- Пока в остове осталось хотя бы две вершины, взорвем предка самого глубокого листа, а также всех его потомков. Чтобы найти самый глубокий лист, отсортируем все вершины по убыванию глубины. Заметим, что самая глубокая вершина, которая ещё не была удалена, обязательно является листом.
- Если в конце остался один корень, то взорвем его вместе с любым из его сыновей (такой сын найдется, потому что корень не изолированная вершина).
Время работы:
- Сортировка: $$$\mathcal{O}(n \log n)$$$ или $$$\mathcal{O}(n)$$$ подсчетом.
- Алгоритм: $$$\mathcal{O}(1)$$$ на каждой итерации. Всего итераций $$$\mathcal{O}(n)$$$, поэтому суммарное время работы $$$\mathcal{O}(n)$$$.