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

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

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

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

, где

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

— рёбер.

Algorithmus

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

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

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

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

. Тогда, если

текущее edge

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

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

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

, то vertex

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

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

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

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

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

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

в

)

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

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

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

из

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

Итак, пусть

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

. Теперь введём Array

, который

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

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

вершину

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

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

, а

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

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

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

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

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

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

, что

.

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

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

,

то vertex

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

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

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

Implementierung

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

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

,

,

и

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

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 значение, равное максимально возможному числу вершин во Eingabeном Graphе.

Функция

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

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

Задачи в online judges

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

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

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