Идея

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

По условию подозрительный маршрут — это замкнутый путь по дорогам, где:

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

Так как в графе нет петель и кратных рёбер, это в точности означает наличие обычного цикла.

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

Наблюдения

1. Граф неориентированный, поэтому каждое ребро u - v хранится дважды:

   • в списке соседей u есть v;
   • в списке соседей v есть u.

2. Если во время обхода из вершины v мы видим соседа to:

   • если to ещё не посещён, продолжаем обход;
   • если to уже посещён и to не является родителем v, то найден цикл.

3. Почему нужно проверять именно to != parent:

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

4. Граф может быть несвязным, значит, запускать обход нужно из каждой ещё не посещённой вершины.

Алгоритм

Будем хранить граф списками смежности.

1. Считываем n и m.
2. Строим список смежности g.
3. Создаём массив used, где used[v] показывает, посещали ли вершину v.
4. Для каждой вершины start от 1 до n:
   • если она уже посещена, пропускаем;
   • иначе запускаем из неё итеративный DFS с помощью стека;
   • в стеке храним пары (v, parent).
5. Пока стек не пуст:
   • достаём вершину v и её родителя parent;
   • перебираем всех соседей to вершины v;
   • если to не посещён, помечаем его и кладём в стек как (to, v);
   • если to уже посещён и to != parent, сразу выводим YES.
6. Если весь граф просмотрен и такой ситуации не возникло, выводим NO.

Почему это работает

Рассмотрим две стороны.

Если алгоритм вывел YES

Это произошло в момент, когда из вершины v мы нашли соседа to, который:

• уже был посещён;
• не является родителем v.

Значит, существует путь обхода до v и путь обхода до to, и при этом есть ребро v - to, которое не является тем ребром, по которому мы пришли назад к родителю. В неориентированном графе такая ситуация означает наличие цикла.

Иначе говоря, мы нашли «замыкание» пути, которое образует цикл.

Если в графе есть цикл

Пусть в некоторой компоненте связности есть цикл. При обходе DFS мы рано или поздно посетим все вершины этого цикла. Когда будем обрабатывать очередную вершину цикла, обнаружится ребро в уже посещённую вершину цикла, которая не является родителем. Тогда алгоритм сработает и выведет YES.

Почему не бывает ложного срабатывания

Единственный случай, когда из вершины ведёт ребро в уже посещённую вершину без цикла, — это возврат к родителю по тому же самому ребру. Но такой случай мы специально исключаем проверкой to != parent.

Значит, алгоритм выводит YES тогда и только тогда, когда в графе есть цикл.

Сложность

Пусть в графе n вершин и m рёбер.

• Построение графа: O(m)
• Обход графа: O(n + m)

Итоговая сложность: O(n + m)

Память:

• список смежности: O(n + m)
• массив посещения и стек: O(n)

Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

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

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

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

        vector<pair<int, int>> st;
        st.push_back({start, 0});
        used[start] = 1;

        while (!st.empty()) {
            int v = st.back().first;
            int parent = st.back().second;
            st.pop_back();

            for (int to : g[v]) {
                if (!used[to]) {
                    used[to] = 1;
                    st.push_back({to, v});
                } else if (to != parent) {
                    cout << "YES\n";
                    return 0;
                }
            }
        }
    }

    cout << "NO\n";
    return 0;
}

Код на Python 3

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

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

used = [False] * (n + 1)

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

    stack = [(start, 0)]
    used[start] = True

    while stack:
        v, parent = stack.pop()

        for to in g[v]:
            if not used[to]:
                used[to] = True
                stack.append((to, v))
            elif to != parent:
                print("YES")
                raise SystemExit

print("NO")