Циклы в графе. Двудольность

void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) {
    visited[v] = 1;
    for (int to : g[v]) {
        if (!visited[to])
            dfs(graph, to, visited);
        else if (visited[to] == 1)
            /* граф содержит цикл */;   
    }
    visited[v] = 2;
}

for (int v = 0; v < graph.size(); v++)
    if (!visited[v])
        dfs(graph, v, visited);

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

• ACMP #151 — Банкет
• ACMP #152 — Построение
• Timus #1080 — Раскраска карты

Ссылки

• e-maxx.ru — Проверка графа на ацикличность и нахождение цикла
• neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе
• brestprog — Проверка графа на наличие циклов (рассматриваются циклы в неориентированных графах)
• brestprog — Двудольные графы. Проверка графа на двудольность
• algorithmica.org — Графы. Поиск в глубину
• algorithmica.org — Продвинутый DFS
• informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2
• Калинин П. Поиск в глубину
• Лахно А. Поиск в глубину и его применение
• VisuAlgo — Graph Traversal