Мосты. Компоненты рёберной двусвязности: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
* Для каждой вершины <tt>v</tt> будем подсчитывать время входа <tt>tIn[v]</tt> и величину <tt>tUp[v]</tt> — минимальное <tt>tIn</tt> для некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру. | * Для каждой вершины <tt>v</tt> будем подсчитывать время входа <tt>tIn[v]</tt> и величину <tt>tUp[v]</tt> — минимальное <tt>tIn</tt> для некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру. | ||
* Ребро (<tt>v</tt> — <tt>u</tt>) является мостом, если из поддерева вершины <tt> | * Ребро (<tt>v</tt> — <tt>u</tt>) является мостом, если из поддерева вершины <tt>u</tt> в дереве обхода в глубину нет обратных рёбер в вершину <tt>v</tt> или её предков (<tt>tUp[u] > tIn[v]</tt>). | ||
vector<int> g[V_CNT]; | vector<int> g[V_CNT]; | ||
| Строка 37: | Строка 37: | ||
* [http://ejudge.btty.su/bmstu/addon/docs/articles/moscow2006-dfs.pdf Лахно А. П. Поиск в глубину и его применение] | * [http://ejudge.btty.su/bmstu/addon/docs/articles/moscow2006-dfs.pdf Лахно А. П. Поиск в глубину и его применение] | ||
* [http://visualgo.net/dfsbfs.html VisuAlgo — Graph Traversal] | * [http://visualgo.net/dfsbfs.html VisuAlgo — Graph Traversal] | ||
* [http://github.com/indy256/codelibrary/blob/master/java/src/ | * [http://github.com/indy256/codelibrary/blob/master/java/src/Biconnectivity.java CodeLibrary — Biconnected components, bridges and cut points] | ||
* [http://github.com/ADJA/algos/blob/master/Graphs/BridgesSearch.cpp Algos — Algorithm for finding all bridges in the graph] | * [http://github.com/ADJA/algos/blob/master/Graphs/BridgesSearch.cpp Algos — Algorithm for finding all bridges in the graph] | ||
[[Category:Поиск в глубину и его приложения]] | [[Category:Поиск в глубину и его приложения]] | ||
Версия от 07:15, 11 декабря 2014
- Для каждой вершины v будем подсчитывать время входа tIn[v] и величину tUp[v] — минимальное tIn для некоторой вершины, достижимой из текущего поддерева переходом по одному обратному ребру.
- Ребро (v — u) является мостом, если из поддерева вершины u в дереве обхода в глубину нет обратных рёбер в вершину v или её предков (tUp[u] > tIn[v]).
vector<int> g[V_CNT];
bool u[V_CNT];
int tIn[V_CNT], tUp[V_CNT], timer;
void dfs(int v, int parent = -1) {
u[v] = 1;
tUp[v] = tIn[v] = timer++;
for (int i = 0; i < g[v].size(); i++) {
if (!u[g[v][i]]) {
dfs(g[v][i], v);
tUp[v] = min(tUp[v], tUp[g[v][i]]);
if (tUp[g[v][i]] > tIn[v])
/* (v, g[v][i]) - мост */;
} else if (g[v][i] != parent)
tUp[v] = min(tUp[v], tIn[g[v][i]]);
}
}
for (int i = 0; i < V_CNT; i++)
u[i] = tIn[i] = tUp[i] = 0;
timer = 0;
for (int i = 0; i < V_CNT; i++)
if (!u[i])
dfs(i);
Ссылки на задачи
Ссылки
- e-maxx.ru — Поиск мостов
- neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска мостов
- neerc.ifmo.ru/wiki — Построение компонент реберной двусвязности
- informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
- Лахно А. П. Поиск в глубину и его применение
- VisuAlgo — Graph Traversal
- CodeLibrary — Biconnected components, bridges and cut points
- Algos — Algorithm for finding all bridges in the graph