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

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

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

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

, где

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

— рёбер.

算法

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

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

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

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

. Тогда, если

текущее edge

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

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

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

, то vertex

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

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

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

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

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

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

в

)

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

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

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

из

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

Итак, пусть

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

. Теперь введём 数组

, который

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

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

вершину

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

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

, а

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

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

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

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

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

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

, что

.

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

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

,

то vertex

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

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

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

实现

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

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

,

,

и

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

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);

}

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

должно быть заgiven значение, равное максимально возможному числу вершин во 输入ном 图е.

Функция

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

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

Задачи в online judges

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

● UVA #10199 "Tourist Guide" [Complexity: низкая]

● UVA #315 "Network" [Complexity: низкая]