Циклы в графе. Двудольность: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (→Ссылки) |
Ctrlalt (обсуждение | вклад) (→Ссылки) |
||
| Строка 29: | Строка 29: | ||
* [http://brestprog.neocities.org/lections/graphcycles.html brestprog.neocities.org — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах) | * [http://brestprog.neocities.org/lections/graphcycles.html brestprog.neocities.org — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах) | ||
* [http://brestprog.neocities.org/lections/bipartite.html brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность] | * [http://brestprog.neocities.org/lections/bipartite.html brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность] | ||
* [http://algorithmica.org/tg/dfs 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:46, 30 августа 2019
vector<int> g[V_CNT];
int u[V_CNT];
void dfs(int v) {
u[v] = 1;
for (int i = 0; i < g[v].size(); i++) {
if (u[g[v][i]] == 1)
/* граф содержит цикл */;
if (!u[g[v][i]])
dfs(g[v][i]);
}
u[v] = 2;
}
for (int i = 0; i < V_CNT; i++)
u[i] = 0;
for (int i = 0; i < V_CNT; i++)
if (!u[i])
dfs(i);
Ссылки на задачи
Ссылки
- e-maxx.ru — Проверка графа на ацикличность и нахождение цикла
- neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе
- brestprog.neocities.org — Проверка графа на наличие циклов (рассматриваются циклы в неориентированных графах)
- brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность
- algorithmica.org — Графы. Поиск в глубину
- informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
- Калинин П. Поиск в глубину
- Лахно А. Поиск в глубину и его применение
- VisuAlgo — Graph Traversal