Разбор задачи «Кольцевые маршруты»

Идея задачи

Дан неориентированный граф. Нужно посчитать количество таких компонент связности, которые являются простыми циклами.

Простой цикл — это компонентa, где:

• из любой вершины можно добраться до любой другой;
• каждая вершина имеет ровно две соседние вершины внутри этой компоненты.

Именно такие компоненты и нужно найти.

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

Связная компонента является простым циклом тогда и только тогда, когда степень каждой вершины в этой компоненте равна 2.

Почему это верно

Если компонента — цикл

Тогда у каждой вершины в этом цикле ровно два соседа:

• один предыдущий,
• один следующий.

Значит, степень каждой вершины равна 2.

Если компонента связная и у всех вершин степень 2

Тогда:

• в компоненте нет тупиков;
• в компоненте нет развилок;
• из любой вершины можно идти по рёбрам дальше, и из-за конечности графа мы обязательно придём в уже посещённую вершину;
• так как степень везде ровно 2 и компонента связная, вся компонента образует один замкнутый цикл.

Значит, условие действительно является точным критерием.

План решения

1. Считать граф.
2. Построить список смежности.
3. Запустить обход графа по всем вершинам.
4. Для каждой непосещённой вершины найти всю её компоненту связности.
5. Проверить, что у всех вершин этой компоненты степень равна 2.
6. Если это так, увеличить ответ на 1.

Как искать компоненты связности

Можно использовать:

• DFS,
• BFS,
• стек,
• очередь.

В этой задаче удобно использовать итеративный DFS через стек.

Это безопасно на больших ограничениях и не вызывает проблем с глубиной рекурсии.

Разберём на примерах

Пример 1

Граф:

• 1–2
• 2–3
• 3–1

Это треугольник.

У каждой вершины степень 2, компонентa связная, значит это цикл.

Пример 2

Граф:

• 1–2
• 2–3
• 3–4

Это путь.

Степени вершин:

• 1 → 1
• 2 → 2
• 3 → 2
• 4 → 1

Не все степени равны 2, значит это не цикл.

Пример 3

Граф в форме «восьмёрки»

Если два цикла имеют общую вершину, то в общей вершине степень будет 4.
Значит такая компонентa не является простым циклом.

Почему не нужно отдельно искать циклы

Иногда хочется проверять:

• число вершин;
• число рёбер;
• наличие цикла специальными алгоритмами.

Но здесь есть более простой критерий:

если компонентa связная и все степени равны 2, то это цикл.

Этого полностью достаточно.

Алгоритм

Для каждой вершины:

• если она уже посещена, пропускаем;
• иначе запускаем обход и собираем все вершины текущей компоненты;
• после этого проверяем степени всех собранных вершин;
• если каждая степень равна 2, увеличиваем ответ.

Оценка сложности

Пусть:

• n — число вершин,
• m — число рёбер.

Тогда:

• каждую вершину мы посещаем один раз;
• каждое ребро просматриваем не более двух раз.

Итоговая сложность:

• по времени: O(n + m)
• по памяти: O(n + m)

Это подходит для больших ограничений.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    vector<bool> used(n + 1, false);
    int answer = 0;

    for (int start = 1; start <= n; start++) {
        if (used[start]) continue;

        vector<int> comp;
        stack<int> st;
        st.push(start);
        used[start] = true;

        while (!st.empty()) {
            int v = st.top();
            st.pop();
            comp.push_back(v);

            for (int to : g[v]) {
                if (!used[to]) {
                    used[to] = true;
                    st.push(to);
                }
            }
        }

        bool isCycle = true;
        for (int v : comp) {
            if (deg[v] != 2) {
                isCycle = false;
                break;
            }
        }

        if (isCycle) {
            answer++;
        }
    }

    cout << answer << '\n';
    return 0;
}

Решение на Python

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]
deg = [0] * (n + 1)

for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)
    deg[u] += 1
    deg[v] += 1

used = [False] * (n + 1)
answer = 0

for start in range(1, n + 1):
    if used[start]:
        continue

    stack = [start]
    used[start] = True
    comp = []

    while stack:
        v = stack.pop()
        comp.append(v)

        for to in g[v]:
            if not used[to]:
                used[to] = True
                stack.append(to)

    ok = True
    for v in comp:
        if deg[v] != 2:
            ok = False
            break

    if ok:
        answer += 1

print(answer)

Пошаговое объяснение кода

1. Считывание графа

Мы сохраняем граф в список смежности:

• g[v] — список соседей вершины v;
• deg[v] — степень вершины v.

2. Массив посещения

Массив used нужен, чтобы не обходить одну и ту же компоненту несколько раз.

3. Обход компоненты

Как только нашли непосещённую вершину, запускаем DFS и собираем все вершины этой компоненты в массив comp.

4. Проверка компоненты

После обхода смотрим на каждую вершину из comp.

Если хотя бы у одной степень не равна 2, то компонентa не подходит.

Если у всех степень 2, значит это простой цикл.

Типичные ошибки

Ошибка 1. Проверять только наличие цикла

Наличие цикла недостаточно.

Например, если есть цикл и к нему приделан хвост, то цикл в графе есть, но вся компонентa уже не является простым циклом.

Ошибка 2. Не разбивать граф на компоненты

Нужно проверять именно каждую компоненту связности отдельно, а не весь граф сразу.

Ошибка 3. Использовать рекурсивный DFS без осторожности

На больших графах рекурсия может привести к переполнению стека.

Поэтому удобнее использовать итеративный обход.

Ошибка 4. Считать, что две вершины с двумя рёбрами образуют цикл

В задаче граф без кратных рёбер, поэтому цикл должен иметь как минимум 3 вершины.
Компонента из двух вершин с одним ребром не подходит, так как степени равны 1.

Что важно запомнить

Главная идея задачи очень короткая:

Нужно найти компоненты связности, в которых у каждой вершины степень равна 2.

Это и есть все циклические компоненты.

Вывод

Задача решается через обычный обход компонент связности.
Самое важное наблюдение — критерий простого цикла через степени вершин.

Это делает решение коротким, эффективным и удобным в реализации.