Числа компонент связности после удаления к вершинам

Question

Я пытаюсь решить следующую задачу графика:

Мы дали общий невзвешенный и неориентированный граф и к (к < | V |) вершин, которые уже известных заранее. Вершины удаляются последовательно. После каждого удаления, сколько подключенных компонентов есть?

Я думал использовать алгоритм Tarján в на каждый шаг, чтобы проверить, если текущая вершина будет удален является разрез вершины, так что, когда выполняется удаление, мы можем просто добавить количество соседей числа подключенных компонентов , Сложностью этого алгоритма является O (V (V + E)).

Мне сказали, что для выполнения этой задачи существует алгоритм O (V + E). Но я не могу понять. Исследование Google также не показывает многого. Может ли кто-нибудь мне посоветовать?

Answer 1

Мы можем использовать тот факт, что вершины известны заранее.

Решите проблему «обратного»: задайте граф и вершины списка, которые ДОБАВЛЯЕТСЯ к нему последовательно, вычислите количество связанных компонентов в графе после каждой структуры добавления.

Решение довольно просто: мы можем поддерживать структуру объединения непересекающихся множеств и добавлять все ребра, инцидентные вершине, к графику (легко сохранить количество компонентов в этой структуре: изначально оно равно числу вершин и уменьшается на единицу, когда фактически происходит объединение).

Исходная задача сводятся к «реверсу» один следующим образом:

1. Давайте добавим все ребра, которые не падает ни одному из удаленных вершин несвязного множественного объединения.

2. Теперь мы можем отменить список удаленных вершин и добавить их один за другим, как описано выше.

3. После этого нам нужно отменить результирующий список, содержащий количество компонентов.

Примечание: это решение не является на самом деле O(V + E), его O(V + E * alpha(V)), где alpha(x) есть функция, обратная Аккермана. Он очень близок к линейным для всех практических целей.