Мосты. Компоненты рёберной двусвязности: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 33: Строка 33:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BC%D0%BE%D1%81%D1%82%D0%BE%D0%B2 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска мостов]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D0%BC%D0%BE%D1%81%D1%82%D0%BE%D0%B2 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска мостов]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%80%D0%B5%D0%B1%D0%B5%D1%80%D0%BD%D0%BE%D0%B9_%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki — Построение компонент реберной двусвязности]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%80%D0%B5%D0%B1%D0%B5%D1%80%D0%BD%D0%BE%D0%B9_%D0%B4%D0%B2%D1%83%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki — Построение компонент реберной двусвязности]
* [http://algorithmica.org/tg/bridges algorithmica.org — Мосты и точки сочленения]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]
* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]
* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]

Версия от 13:59, 30 августа 2019

  • Для каждой вершины v будем подсчитывать глубину depth[v] и величину upDepth[v] — минимальную глубину некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
  • Ребро (v — u) является мостом, если из поддерева вершины u в дереве обхода в глубину нет обратных рёбер в вершину v или её предков (upDepth[u] > depth[v]).
vector<int> g[V_CNT];
bool u[V_CNT];
int depth[V_CNT], upDepth[V_CNT]; 

void dfs(int v, int parent = -1) {
    u[v] = 1;
    depth[v] = upDepth[v] = (parent == -1 ? 0 : depth[parent] + 1);
    for (int i = 0; i < g[v].size(); i++) {
        if (!u[g[v][i]]) {
            dfs(g[v][i], v);
            upDepth[v] = min(upDepth[v], upDepth[g[v][i]]);
            if (upDepth[g[v][i]] > depth[v])
                /* (v, g[v][i]) - мост */;
        } else if (g[v][i] != parent)
            upDepth[v] = min(upDepth[v], depth[g[v][i]]);
    }     
}

for (int i = 0; i < V_CNT; i++)
    u[i] = 0;
for (int i = 0; i < V_CNT; i++)
    if (!u[i])
        dfs(i);

Ссылки на задачи

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Мосты._Компоненты_рёберной_двусвязности&oldid=2412