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

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