Кактусы и цикл чётной длины

Задача: найти в неориентированном графе простой цикл чётной длины или сказать, что его нет.

Цикл нечётной длины искать умеют: граф двудолен тогда и только тогда, когда нечётных циклов нет, а двудольность проверяется покраской в два цвета. С чётными такого критерия нет.

Ключевое наблюдение

Пусть два нечётных цикла имеют общее ребро. Возьмём их симметрическую разность: длина получается $|A| + |B| - 2|C|$, где $C$ — общая часть. Сумма двух нечётных чётна, вычитание чётного её не меняет — значит, чётный цикл существует.

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

Значит, если в графе есть два цикла с общим ребром, ответ «да» без всякого поиска.

Остаётся кактус

Граф, в котором никакие два простых цикла не имеют общего ребра, называется рёберным кактусом. Название от того, что он похож на дерево, у которого некоторые вершины «раздулись» в циклы.

В кактусе циклы не пересекаются по рёбрам, поэтому смотреть на них можно по отдельности: чётный цикл есть тогда и только тогда, когда чётен хотя бы один из них.

Итого алгоритм:

1. Проверить, кактус ли граф. Если нет — ответ «да».
2. Если кактус — перебрать его циклы и посмотреть на их длины.

Проверка на кактус

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

Каждое обратное ребро задаёт ровно один цикл: само ребро плюс путь по дереву между его концами.

Граф — кактус тогда и только тогда, когда каждое ребро дерева покрыто не более чем одним обратным ребром. Если два обратных ребра покрывают одно и то же ребро дерева, их циклы делят это ребро.

void dfs(int v) {
    for (auto [u, id] : g[v]) {
        if (id == parEdge[v]) continue;              // ребро к родителю, ровно один раз
        if (h[u] == -1) {                            // ребро дерева
            h[u] = h[v] + 1; par[u] = v; parEdge[u] = id;
            dfs(u);
        } else if (h[u] < h[v]) {                    // обратное ребро вверх
            for (int x = v; x != u; x = par[x]) {
                int e = parEdge[x];
                if (covered[e]) { notCactus = true; return; }
                covered[e] = true;
            }
        }
    }
}

Проверено: на 100 000 случайных графов результат совпал с перебором всех простых циклов и попарной проверкой на общие рёбра.

Почему подъём по циклу не даёт квадрат

Внутренний цикл выглядит опасно: для каждого обратного ребра мы поднимаемся по дереву.

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

Приём знакомый: работу оценивают не по одной операции, а суммарно. Тот же ход в очереди на двух стеках и в префикс-функции.

Осторожно с кратными рёбрами

Два ребра между одной парой вершин — это цикл длины 2, и он чётный. В коде выше это учтено: parEdge хранит номер ребра, а не вершину, поэтому параллельное ребро распознаётся как обратное.

Наивная проверка if (u == parent) continue; пропустила бы оба и выдала неверный ответ. Та же ловушка, что при поиске мостов.