Дерево обхода и поиск циклов

Запустим обход в глубину и оставим только те рёбра, по которым он реально прошёл. Получится дерево — дерево обхода. Остальные рёбра никуда не делись, и их полезно классифицировать.

Четыре вида рёбер

вид	куда ведёт
древесное	в непосещённого потомка, по нему прошёл обход
обратное	в предка, уже посещённого
прямое	в потомка, но обход прошёл не по нему
перекрёстное	в вершину из уже завершённого поддерева сбоку

В неориентированном графе бывают только древесные и обратные.

Прямых нет: если ребро ведёт в потомка, то к моменту, когда обход дошёл до этого потомка, ребро уже рассматривалось — и потомок был бы посещён по нему.

Перекрёстных тоже нет: пусть ребро соединяет $u$ и $v$ из разных поддеревьев. Тогда, обходя то из них, куда обход попал раньше, мы бы прошли по этому ребру и второе поддерево оказалось бы внутри первого.

В ориентированном графе бывают все четыре.

Циклы в неориентированном графе

Цикл — это спуск по древесным рёбрам плюс одно обратное. Значит, цикл есть тогда и только тогда, когда найдётся обратное ребро.

Единственная тонкость: ребро в родителя обратным считать нельзя — мы только что по нему пришли.

vector<int> parent;

bool dfs(int v, int p) {
    used[v] = 1;
    parent[v] = p;
    for (int to : g[v]) {
        if (to == p) continue;              // ребро назад к родителю
        if (used[to]) { /* нашли цикл v -> to */ return true; }
        if (dfs(to, v)) return true;
    }
    return false;
}

Проверка to == p пропускает одно ребро в родителя. Если между $v$ и $p$ есть кратное ребро, это уже настоящий цикл длины 2, и пропускать нужно ровно один экземпляр, а не все. Аккуратнее всего хранить номер ребра, по которому пришли, а не номер вершины.

Восстановление цикла. Нашли обратное ребро из $v$ в $u$ — поднимаемся по родителям от $v$, пока не дойдём до $u$:

vector<int> cycle;
for (int x = v; x != u; x = parent[x]) cycle.push_back(x);
cycle.push_back(u);
reverse(cycle.begin(), cycle.end());

Циклы в ориентированном графе

Здесь двух состояний мало. Посещённая вершина может быть либо предком (мы внутри её вызова), либо вершиной из завершённого поддерева — и это разные случаи: первое даёт цикл, второе нет.

Поэтому красим в три цвета:

• 0 — не посещена;
• 1 — вошли, но ещё не вышли (вершина на текущем пути от корня);
• 2 — вышли, поддерево полностью обработано.

vector<int> color;

bool dfs(int v) {
    color[v] = 1;
    for (int to : g[v]) {
        if (color[to] == 1) return true;    // обратное ребро — цикл
        if (color[to] == 0 && dfs(to)) return true;
    }
    color[v] = 2;
    return false;
}

Ребро в вершину цвета 2 — прямое или перекрёстное, цикла не даёт. Ребро в вершину цвета 1 — обратное, и цикл найден: он проходит по текущему пути от to до v.

Проверять на родителя здесь не нужно: ребро $v \to u$ и ребро $u \to v$ — разные рёбра, и вместе они образуют настоящий цикл длины 2.

Восстановление цикла — то же самое, подъём по родителям. Только результат нужно развернуть: в ориентированном графе порядок вершин в цикле существенен.

Проверено вместе с топологической сортировкой: на двадцати тысячах случайных ориентированных графов наличие цикла, найденное трёхцветным обходом, совпало с проверкой через транзитивное замыкание.

Сводка критериев

задача	критерий
цикл в неориентированном	есть обратное ребро (кроме ребра в родителя)
цикл в ориентированном	есть ребро в вершину цвета 1
нечётный цикл	граф не двудолен
граф — дерево	связен и $m = n - 1$
граф — лес	нет циклов

Для неориентированного графа есть и совсем дешёвая проверка: если $m \ge n$, цикл точно есть. Обходить нужно только когда $m < n$ — и тогда достаточно сравнить число компонент с $n - m$.