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

vector<vector<int>> g(n);
vector<int> visited(n); // 0 - ещё не были в вершине, 1 - вошли, но ещё не вышли из неё, 2 - уже обработали её

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

for (int v = 0; v < n; v++)
    if (!visited[v])
        dfs(v);

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

• 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