Циклы в графе. Двудольность: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 30: Строка 30:
* [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://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]
* [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:57, 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);

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

Ссылки

Источник — https://acm.khpnets.info/w39/index.php?title=Циклы_в_графе._Двудольность&oldid=2410