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: низкая]