Компоненты сильной связности. Алгоритм Косараю-Шарира: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
Строка 3: | Строка 3: | ||
* Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки"). | * Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки"). | ||
vector<int> g | vector<vector<int>> g(n), gr(n); | ||
int | vector<int> visited(n); | ||
vector<int> order; | vector<int> order; | ||
void dfs1(int v) { | void dfs1(int v) { | ||
visited[v] = 1; | |||
for (int | for (int to : g[v]) | ||
if (! | if (!visited[to]) | ||
dfs1( | dfs1(to); | ||
order.push_back(v); | order.push_back(v); | ||
} | } | ||
void dfs2(int v, int | void dfs2(int v, int component) { | ||
visited[v] = component; | |||
for (int | for (int to : gr[v]) | ||
if (! | if (!visited[to]) | ||
dfs2( | dfs2(to, component); | ||
} | } | ||
for (int | for (int v = 0; v < n; v++) | ||
if (!visited[v]) | |||
dfs1(v); | |||
if (! | |||
dfs1( | |||
reverse(order.begin(), order.end()); | reverse(order.begin(), order.end()); | ||
fill(visited.begin(), visited.end(), 0); | |||
int | |||
for (int | int componentsCount = 0; | ||
if (! | for (int v : order) | ||
dfs2( | if (!visited[v]) | ||
dfs2(v, ++componentsCount); | |||
Построение конденсации: | Построение конденсации: | ||
unordered_map<int, vector<int>> g, gr, gc; | unordered_map<int, vector<int>> g, gr, gc; | ||
unordered_set<int> visited; | unordered_set<int> visited; | ||
vector<int> order; | vector<int> order; | ||
void dfs1(int v) { | void dfs1(int v) { | ||
visited.insert(v); | visited.insert(v); | ||
Строка 51: | Строка 50: | ||
unordered_map<int, int> scc; | unordered_map<int, int> scc; | ||
void dfs2(int v, int | |||
void dfs2(int v, int component) { | |||
visited.insert(v); | visited.insert(v); | ||
scc[v] = | scc[v] = component; | ||
for (int to : gr[v]) { | for (int to : gr[v]) { | ||
if (!visited.count(to)) | if (!visited.count(to)) | ||
dfs2(to, | dfs2(to, component); | ||
} | } | ||
} | } | ||
Строка 79: | Строка 79: | ||
visited.clear(); | visited.clear(); | ||
int sccN = 0; | int sccN = 0; | ||
for (int | for (int v : order) { | ||
if (!visited.count( | if (!visited.count(v)) | ||
dfs2( | dfs2(v, sccN++); | ||
} | } | ||
Версия от 16:02, 15 февраля 2020
- Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
- Транспонируем граф.
- Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").
vector<vector<int>> g(n), gr(n); vector<int> visited(n); vector<int> order; void dfs1(int v) { visited[v] = 1; for (int to : g[v]) if (!visited[to]) dfs1(to); order.push_back(v); } void dfs2(int v, int component) { visited[v] = component; for (int to : gr[v]) if (!visited[to]) dfs2(to, component); } for (int v = 0; v < n; v++) if (!visited[v]) dfs1(v); reverse(order.begin(), order.end()); fill(visited.begin(), visited.end(), 0); int componentsCount = 0; for (int v : order) if (!visited[v]) dfs2(v, ++componentsCount);
Построение конденсации:
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 component) { visited.insert(v); scc[v] = component; for (int to : gr[v]) { if (!visited.count(to)) dfs2(to, component); } } 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 v : order) { if (!visited.count(v)) dfs2(v, 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