найти общее количество компонентов в графике

Question

У меня есть граф с N узлами и M ребрами. Это один компонент.

Теперь мне нужно удалить один узел из графа, удаление этого узла может разделить граф на 1,2 или более компонентов. Количество таких компонентов требуется для каждого удаленного узла. Обратите внимание, что в любой момент времени удаляется только один узел.

Мне нужно сделать это для всех узлов графика за линейное время.

Возможно ли это за линейное время? Я могу сделать это в O (n ^ 2), запустив DFS для каждого узла.

Answer 1

Прочитайте некоторые онлайн-ресурсы о «Точке артикуляции». Я надеюсь, что вы получите свой ответ. https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Answer 2

Да, вы можете сделать это за линейное время. Сначала вам нужно вычислить двусвязные компоненты вашего графа https://en.wikipedia.org/wiki/Biconnected_component,, которые вы можете сделать за O (| V | + | E |), используя версию алгоритма Тарьяна. Затем для каждого узла вам просто нужно увидеть количество смежных двусвязных компонентов, которые вы можете снова вычислить за O (| V | + | E |).