Разбор задачи «Бездна и кольцевой риф»

Идея задачи

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

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

Именно такую структуру и нужно распознать.

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

Если граф состоит из одного цикла и нескольких деревьев, подвешенных к его вершинам, то:

• граф обязательно связный;
• в нём ровно один цикл.

Для неориентированного графа это очень удобно.

Факт

Для связного неориентированного графа:

• если m = n - 1, то это дерево;
• если m = n, то в графе ровно один цикл;
• если m > n, то циклов больше одного.

Здесь:

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

Значит, граф подходит под условие тогда и только тогда, когда:

1. он связный;
2. у него число рёбер равно числу вершин, то есть m = n.

Почему этого достаточно

Предположим, что граф связный и m = n.

Тогда число независимых циклов в неориентированном графе равно:

m - n + 1

Подставим m = n:

n - n + 1 = 1

Получается, в графе ровно один цикл.

Так как по условию нет петель и кратных рёбер, этот цикл автоматически простой и имеет длину хотя бы 3.

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

Именно это и требуется по условию.

Что проверять в программе

Нужно сделать всего две проверки:

1. Проверить, что m == n

Если это не так, ответ сразу NO.

2. Проверить связность графа

Запускаем обход графа из любой вершины, например из вершины 1.

Подойдёт:

• DFS;
• BFS.

Если после обхода не все вершины посещены, граф несвязный, значит ответ NO.

Если все вершины посещены и m == n, то ответ FHTAGN!.

Алгоритм

1. Считать n и m.
2. Построить список смежности.
3. Если m != n, вывести NO.
4. Иначе выполнить DFS/BFS из вершины 1.
5. Проверить, все ли вершины были посещены.
6. Если да — вывести FHTAGN!, иначе NO.

Доказательство корректности

Докажем, что алгоритм работает правильно.

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

Это означает, что:

• m = n;
• граф связный.

Для связного неориентированного графа число независимых циклов равно m - n + 1.
Следовательно, число циклов равно:

n - n + 1 = 1

То есть цикл ровно один.

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

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

Если граф действительно имеет нужную структуру

Тогда он состоит из:

• одного простого цикла;
• деревьев, подвешенных к его вершинам.

Такой граф:

• обязательно связный;
• содержит ровно один цикл.

А для связного неориентированного графа с ровно одним циклом всегда выполняется m = n.

Значит, алгоритм обязательно пройдёт обе проверки и выведет FHTAGN!.

Вывод

Алгоритм выводит FHTAGN! тогда и только тогда, когда граф подходит под условие задачи.
Следовательно, он корректен.

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

Построение графа занимает O(m).

Один обход DFS или BFS работает за O(n + m).

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

O(n + m)

Память:

O(n + m)

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

Ошибка 1. Проверять только m == n

Этого недостаточно.

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

Ошибка 2. Искать цикл сложными способами

В этой задаче не нужно отдельно искать сам цикл.
Нам достаточно использовать свойство связного графа и число рёбер.

Ошибка 3. Забыть, что граф неориентированный

При построении списка смежности нужно добавлять ребро в обе стороны.

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

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

vector<vector<int>> g;
vector<int> used;

void dfs(int v) {
    used[v] = 1;
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

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

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

    g.assign(n + 1, {});
    used.assign(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);
    }

    if (m != n) {
        cout << "NO\n";
        return 0;
    }

    dfs(1);

    for (int v = 1; v <= n; v++) {
        if (!used[v]) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "FHTAGN!\n";
    return 0;
}

Пояснение к решению на C++

• g — список смежности графа.
• used[v] показывает, посещали ли мы вершину v.
• Сначала проверяем условие m != n. Если оно выполняется, сразу отвечаем NO.
• Затем запускаем dfs(1) и проверяем, все ли вершины достижимы.
• Если все вершины посещены, граф связный, и при m = n это означает, что цикл ровно один.

Решение на Python

import sys

sys.setrecursionlimit(10**7)

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)

if m != n:
    print("NO")
    sys.exit()

used = [False] * (n + 1)

def dfs(v):
    used[v] = True
    for to in g[v]:
        if not used[to]:
            dfs(to)

dfs(1)

for v in range(1, n + 1):
    if not used[v]:
        print("NO")
        break
else:
    print("FHTAGN!")

Пояснение к решению на Python

Здесь используется тот же самый подход:

• строим неориентированный граф;
• сразу проверяем условие m == n;
• делаем DFS;
• если найдётся непосещённая вершина, граф несвязный.

Если же все вершины посещены, то граф связный и содержит ровно один цикл, значит ответ положительный.

Небольшой разбор примеров

Случай 1

Есть цикл из нескольких вершин, а остальные вершины просто подвешены к нему.
Такой граф подходит.

Случай 2

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

Случай 3

Если появляется ещё один цикл, то это уже не тот вид графа, который нужен в задаче.

Итог

Задача выглядит как проверка специальной структуры графа, но решается очень коротко благодаря важному свойству:

граф подходит тогда и только тогда, когда он связный и в нём m = n.

Поэтому основа решения — это:

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