Для решения можно воспользоваться структурой данных \texttt{std::set}. Посчитаем степени вершин и сложим 
в сет пары $(\text{deg}(v), v)$. На каждом шаге будет доставать все вершины максимальной степени и уменьшать степени их соседей на один. Доставать вершины можно с помощью итератора \texttt{rbegin}, уменьшать степень можно явно удаляя вершину из сета и добавляя вершину со степенью, уменьшенной на один. Для этого полезно хранить текущую степень каждой вершины в массиве. Количество выполненных итераций будет ответом.

Каждая вершина будет уничтожена ровно один раз и в этот момент будут рассмотрены все её соседи. Количество вершин $n$, количество рёбер $m$, стоимость обращения к \texttt{std::set} $O(\log n)$. Асимптотика решения: $O((n + m)\log n)$.

