Компоненты сильной связности. Алгоритм Косараю-Шарира: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
Строка 94: | Строка 94: | ||
* [http://e-maxx.ru/algo/strong_connected_components e-maxx.ru — Поиск компонент сильной связности, построение конденсации графа] | * [http://e-maxx.ru/algo/strong_connected_components e-maxx.ru — Поиск компонент сильной связности, построение конденсации графа] | ||
* [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%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%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%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%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%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/dfs-plus algorithmica.org — Продвинутый DFS] | |||
* [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:58, 30 августа 2019
- Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
- Транспонируем граф.
- Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").
vector<int> g[V_CNT], gR[V_CNT]; int u[V_CNT]; vector<int> order; void dfs1(int v) { u[v] = 1; for (int i = 0; i < g[v].size(); i++) if (!u[g[v][i]]) dfs1(g[v][i]); order.push_back(v); } void dfs2(int v, int k) { u[v] = k; for (int i = 0; i < gR[v].size(); i++) if (!u[gR[v][i]]) dfs2(gR[v][i], k); } for (int i = 0; i < V_CNT; i++) u[i] = 0; for (int i = 0; i < V_CNT; i++) if (!u[i]) dfs1(i); reverse(order.begin(), order.end()); for (int i = 0; i < V_CNT; i++) u[i] = 0; int k = 1; for (int i = 0; i < V_CNT; i++) if (!u[order[i]]) dfs2(order[i], k++);
Построение конденсации:
unordered_map<int, vector<int>> g, gr, gc; unordered_set<int> visited; vector<int> order; void dfs1(int v) { visited.insert(v); for (int to : g[v]) { if (!visited.count(to)) dfs1(to); } order.push_back(v); } unordered_map<int, int> scc; void dfs2(int v, int sccN) { visited.insert(v); scc[v] = sccN; for (int to : gr[v]) { if (!visited.count(to)) dfs2(to, sccN); } } int main() { int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { string a, b; cin >> a >> b; g[a].push_back(b); gr[b].push_back(a); } for (int v = 0; v < n; v++) { if (!visited.count(v)) dfs1(v); } reverse(order.begin(), order.end()); visited.clear(); int sccN = 0; for (int i = 0; i < order.size(); i++) { if (!visited.count(order[i])) dfs2(order[i], sccN++); } for (int v = 0; v < n; v++) { for (int to : g[v]) if (scc[v] != scc[to]) gc[scc[v]].push_back(scc[to]); } }
Ссылки
- e-maxx.ru — Поиск компонент сильной связности, построение конденсации графа
- neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска компонент сильной связности
- algorithmica.org — Продвинутый DFS
- informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
- Калинин П. Поиск в глубину
- Лахно А. Поиск в глубину и его применение
- algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs
- VisuAlgo — Graph Traversal
- CodeLibrary — Strongly connected components. Kosaraju's algorithm