E030. Поиск точек сочленения

Task

Источник: e-maxx.ru/algo, страница PDF 94.

Пусть дан связный неориентированный граф. Точкой сочленения (или точкой артикуляции, англ. "cut vertex" или "articulation point") называется такая вершина, удаление которой делает граф несвязным.

Опишем алгоритм, основанный на поиске в глубину, работающий за

, где

— количество вершин,

— рёбер.

Алгоритм

Запустим обход в глубину из произвольной вершины графа; обозначим её через

. Заметим следующий

факт (который несложно доказать):

● Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины

. Тогда, если

текущее ребро

таково, что из вершины

и из любого её потомка в дереве обхода в глубину нет обратного

ребра в или какого-либо предка вершины

, то вершина

является точкой сочленения. В противном случае, т.е.

если обход в глубину просмотрел все рёбра из вершины

, и не нашёл удовлетворяющего вышеописанным

условиям ребра, то вершина

не является точкой сочленения. (В самом деле, мы этим условием проверяем, нет

ли другого пути из

в

)

● Рассмотрим теперь оставшийся случай:

. Тогда эта вершина является точкой сочленения тогда и только

тогда, когда эта вершина имеет более одного сына в дереве обхода в глубину. (В самом деле, это означает, что, пройдя

из

по произвольному ребру, мы не смогли обойти весь граф, откуда сразу следует, что — точка сочленения). (Ср. формулировку этого критерия с формулировкой критерия для алгоритма поиска мостов.) Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.

Итак, пусть

— это время захода поиска в глубину в вершину

. Теперь введём массив

, который

и позволит нам отвечать на вышеописанные запросы. Время

равно минимуму из времени захода в саму

вершину

, времён захода в каждую вершину

, являющуюся концом некоторого обратного ребра

, а

также из всех значений

для каждой вершины

, являющейся непосредственным сыном

в дереве поиска: (здесь "back edge" — обратное ребро, "tree edge" — ребро дерева)

Тогда, из вершины

или её потомка есть обратное ребро в её предка тогда и только тогда, когда найдётся такой сын

, что

.

Таким образом, если для текущего ребра

(принадлежащего дереву поиска) выполняется

,

то вершина

является точкой сочленения. Для начальной вершины

критерий другой: для этой вершины

надо посчитать число непосредственных сыновей в дереве обхода в глубину.

Реализация

Если говорить о самой реализации, то здесь нам нужно уметь различать три случая: когда мы идём по ребру дерева поиска в глубину, когда идём по обратному ребру, и когда пытаемся пойти по ребру дерева в обратную

сторону. Это, соответственно, случаи

,

,

и

. Таким образом, нам надо передавать в функцию поиска в глубину вершину-предка текущей вершины.

vector<int> g[MAXN];

bool used[MAXN];

int timer, tin[MAXN], fup[MAXN];

void dfs (int v, int p = -1) {

used[v] = true;

tin[v] = fup[v] = timer++;

int children = 0;

for (size_t i=0; i<g[v].size(); ++i) {

int to = g[v][i];

if (to == p)  continue;

if (used[to])

fup[v] = min (fup[v], tin[to]);

else {

dfs (to, v);

fup[v] = min (fup[v], fup[to]);

if (fup[to] >= tin[v] && p != -1)

IS_CUTPOINT(v);

++children;

} }

if (p == -1 && children > 1)

IS_CUTPOINT(v);

}

int main() {

int n;

... чтение n и g ...

timer = 0;

for (int i=0; i<n; ++i)

used[i] = false;

dfs (0);

}

Здесь константе

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

Функция

в коде — это некая функция, которая будет реагировать на то, что вершина

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

Задачи в online judges

Список задач, в которых требуется искать точки сочленения:

● UVA #10199 "Tourist Guide" [сложность: низкая]

● UVA #315 "Network" [сложность: низкая]