Разбор задачи «Лесная сеть сигналов»

Идея задачи

Нам дан неориентированный граф из n вершин и m рёбер. Нужно определить, является ли он правильной сетью, то есть деревом.

Для дерева должны выполняться два свойства:

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

Есть очень удобный критерий:

Неориентированный граф является деревом тогда и только тогда, когда он связный и содержит ровно n - 1 ребро.

Поэтому решение получается коротким:

1. Считываем граф.
2. Проверяем, что m == n - 1.
3. Проверяем, что из одной вершины можно добраться до всех остальных.
4. Если да — ответ yes, иначе no.

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

Разберёмся, почему достаточно именно этих двух условий.

Свойство 1. У дерева ровно n - 1 ребро

Это базовое свойство дерева. Если рёбер меньше, чем n - 1, то все вершины связать не получится.
Если рёбер больше, чем n - 1, то где-то обязательно появится цикл.

Свойство 2. Если граф связный и в нём n - 1 ребро, то это дерево

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

Следовательно, такой граф — дерево.

Алгоритм

1. Считать n и m.
2. Построить список смежности.
3. Если m != n - 1, сразу вывести no.
4. Запустить обход графа из вершины 1.
5. Проверить, все ли вершины были посещены.
6. Если все посещены — вывести yes, иначе no.

Почему удобно использовать BFS или DFS

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

• BFS — обход в ширину;
• DFS — обход в глубину.

В этой задаче разницы почти нет. Мы покажем решение через BFS, потому что оно очень наглядное.

Пример рассуждения

Пусть дан граф:

• 1 - 2
• 2 - 3
• 3 - 4

Здесь:

• все вершины достижимы друг из друга;
• число рёбер равно 3, а число вершин равно 4;
• значит m = n - 1.

Это дерево, ответ yes.

Теперь рассмотрим граф:

• 1 - 2
• 2 - 3
• 3 - 4
• 4 - 1

Тут рёбер уже 4, а вершин тоже 4.
Получается m != n - 1, значит есть цикл, и ответ no.

Реализация на 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);

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

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

    vector<bool> used(n + 1, false);
    queue<int> q;
    q.push(1);
    used[1] = true;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

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

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

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

Разбор решения на C++

Построение графа

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

vector<vector<int>> g(n + 1);

Если есть ребро a-b, то добавляем:

g[a].push_back(b);
g[b].push_back(a);

Так как граф неориентированный, каждое ребро записываем в обе стороны.

Проверка количества рёбер

Сразу делаем важную проверку:

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

Если число рёбер не равно n - 1, граф точно не дерево.

Проверка связности

Запускаем BFS из вершины 1:

queue<int> q;
q.push(1);
used[1] = true;

Пока очередь не пуста, достаём вершину и идём по всем её соседям.
Если сосед ещё не посещён, добавляем его в очередь.

После обхода проверяем, все ли вершины отмечены как посещённые.

Реализация на Python

from collections import deque

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

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

for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

if m != n - 1:
    print("no")
    exit()

used = [False] * (n + 1)
q = deque([1])
used[1] = True

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

for v in range(1, n + 1):
    if not used[v]:
        print("no")
        exit()

print("yes")

Разбор решения на Python

Логика полностью такая же, как и в C++:

• строим список смежности;
• проверяем условие m == n - 1;
• запускаем BFS;
• убеждаемся, что посетили все вершины.

Для очереди удобно использовать deque из модуля collections.

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

Пусть в графе:

• n вершин;
• m рёбер.

Тогда:

• построение графа работает за O(m);
• обход BFS работает за O(n + m).

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

O(n + m)

По памяти:

O(n + m)

Частые ошибки

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

Этого недостаточно.
Например, граф может иметь n - 1 ребро, но состоять из нескольких компонент связности.

Ошибка 2. Проверять только связность

Тоже недостаточно.
Граф может быть связным, но содержать цикл.

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

Если добавить ребро только в одну сторону, обход будет работать неправильно.

Ошибка 4. Использовать вершины от 0, когда во входных данных они от 1

Из-за этого легко получить ошибку индексов или потерять часть вершин.

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

У этой задачи очень полезная идея:

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

• граф связный;
• число рёбер равно n - 1.

Это встречается очень часто в задачах на графы.

Итог

Мы свели задачу к двум простым проверкам:

1. m == n - 1
2. граф связный

Если оба условия выполнены, ответ yes, иначе no.

Это короткое, эффективное и очень надёжное решение.