MAXimal | |
добавлено: 5 Jul 2008 22:26 Содержание [скрыть] Поиск точек сочлененияПусть дан связный неориентированный граф. Точкой сочленения (или точкой артикуляции, англ. "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Список задач, в которых требуется искать точки сочленения:
|