Решение алгоритма графа сделано правильно?

Я наткнулся на проблему из последнего Facebook Hacker Cup (так что это НЕ моя домашняя работа, я просто нахожу ее очень интересной), и я также придумал любопытное, но довольно хорошее решение. Не могли бы вы проверить мою мысль? Вот задание:

Вам дана сеть из N городов и M двунаправленных дорог, соединяющих эти города. Первые K городов важны. Вам нужно убрать минимум количество дорог такое, что в оставшейся сети нет циклов, содержат важные города.Цикл - это последовательность как минимум трех разных такие города, что каждая пара соседних городов соединена дорогой и первый и последний город в последовательности также соединены дорогой.

Входные данные
Первая строка содержит количество тестовых примеров T.

Каждый случай начинается со строки, содержащей целые числа N, M и K, которые представляют количество городов, количество дорог и количество важных городов, соответственно. Города пронумерованы от 0 до N-1, а важные города пронумерованы от 0 до K-1. Следующие M строк содержат два целых числа a [i] и b [i], 0 ≤ i

Гарантируется, что 0 ≤ a [i], b [i]

Выходные данные
Для каждого из тестовых примеров, пронумерованных в порядке от 1 до T, выведите «Case #i:» за которым следует одно целое число, минимальное количество дорог, которые должны быть удалено так, что нет циклов, содержащих важный город.

Ограничения
1 ≤ T ≤ 20
1 ≤ N ≤ 10000
1 ≤ M ≤ 50000
1 ≤ K ≤ N

Пример
В первом примере у нас есть N = 5 городов, соединенных M = 7 дороги и города 0 и 1 важны. Мы можем удалить две дороги, соединяющие (0, 1) и (1, 2), а оставшаяся сеть не будет содержать циклов с важные города. Обратите внимание, что в оставшейся сети есть цикл, который содержит только второстепенные города, и что есть несколько способов удалить две дороги и выполнить все условия.Нельзя удалить только одну дорогу и уничтожить все циклы, в которых находятся важные города.

Пример ввода
1
5 7 2
0 1
1 2
1 4
0 2
2 4
2 3
3 4

Итак, я подумал об этом так: при построении графа давайте создадим отдельный массив, в котором будет храниться информация о том, сколько соседей имеет каждый город (== сколько дорог подключено к данному городу). В данном примере у города 0 2, у города 1 3 и так далее. Назовем эти числа «городской ценностью» конкретного города.

После получения всех входных данных мы просматриваем весь массив значений городов в поисках городов со значением 1. Когда мы добираемся до одного, это означает, что он не может быть в цикле, поэтому мы уменьшаем его значение, «удалить» ( без потери общности) дорога, соединяющая его с единственным соседом и уменьшающая значение соседа. После этого мы рекурсивно переходим к соседу, проверяющему то же самое, если там значение 1 - повторяем схему и рекурсивно идем глубже. Если нет - не трогайте.

После этой операции мы очистили все части графа, которые не являются циклами и не могут быть частью одного. Мы также избавились от всех дорог, которые не имели никакого смысла. Поэтому мы вызываем другую функцию, на этот раз - работающую только с важными городами. Итак, мы берем вершину 1 - после использования функции, описанной в предыдущем абзаце, ее значение не может быть 1 (так как оно уже было бы обнулено функцией), поэтому оно либо 0, либо что-то> 1. В первом случае нам ничего не нужно делать.В последнем случае мы должны сделать значение 1, что достигается удалением значения 1. Как и в предыдущем абзаце, после каждого удаления мы уменьшаем значение как этого города, так и его соседа, также удаляя дорогу.Мы повторяем это для всех k важных городов, суммируя значения 1 для всех важных городов, и это наш ответ.

Есть ли в этом смысл? Для всех тестов, которые я пробовал, он работал, и я хотел бы верить, что это правильно, но я почему-то чувствую, что где-то может быть утечка. Не могли бы вы это проверить? Это хорошо? Если нет, то почему и есть ли что-нибудь правильное в этом мыслительном процессе? :)