1. Идея

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

Это обычная задача на достижимость в неориентированном графе:

• комнаты — это вершины графа;
• линии связи — это рёбра графа;
• сигнал из комнаты 1 может пройти во все комнаты, которые достижимы из вершины 1.

Значит, достаточно обойти граф, начиная с вершины 1, и посчитать, сколько вершин удалось посетить. Если посетили ровно n комнат, то ответ YES, иначе NO.

2. Наблюдения

1. Так как линии двусторонние, граф неориентированный.
   Поэтому для каждой линии u v нужно добавить:

   • v в список соседей u,
   • u в список соседей v.

2. Не нужно искать пути до каждой комнаты отдельно.
   Достаточно один раз выполнить обход из комнаты 1.

3. Подойдут и DFS, и BFS.
   В эталонном решении используется итеративный DFS через стек.

4. Если n = 1, то ответ всегда YES: сигнал уже находится в единственной комнате.

3. Алгоритм

Используем обход в глубину с явным стеком.

1. Считываем n и m.
2. Строим список смежности g.
3. Создаём массив used, где used[v] = True, если комната v уже достигнута сигналом.
4. Кладём комнату 1 в стек, помечаем её посещённой.
5. Пока стек не пуст:
   • достаём вершину v;
   • перебираем всех соседей to вершины v;
   • если сосед ещё не посещён, помечаем его, увеличиваем счётчик посещённых комнат и кладём в стек.
6. После обхода сравниваем число посещённых комнат cnt с n:
   • если cnt == n, выводим YES;
   • иначе выводим NO.

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

Докажем, что алгоритм выдаёт правильный ответ.

Когда мы начинаем обход из комнаты 1, в стек попадает только она. Дальше каждый раз, когда мы извлекаем комнату из стека, мы добавляем в стек все соседние комнаты, в которые ещё не заходили.

Значит:

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

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

Теперь остаётся проверить:

• если достижимы все n комнат, то сигнал дойдёт до всей лаборатории, и нужно вывести YES;
• если хотя бы одна комната не достижима, то сигнал не сможет попасть в неё, и нужно вывести NO.

Значит, алгоритм корректен.

5. Сложность

Пусть n — число комнат, m — число линий связи.

• Построение списка смежности: O(m).
• Обход графа: `O(n + m)``, потому что каждая вершина посещается не более одного раза, а каждое ребро рассматривается не более двух раз.

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

По памяти:

• список смежности хранит все рёбра: O(n + m);
• массив посещения и стек: O(n).

Итоговая память: O(n + m).

6. Код на 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<bool> used(n + 1, false);
    vector<int> st;
    st.push_back(1);
    used[1] = true;
    int cnt = 1;

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

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

    if (cnt == n) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на 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)
stack = [1]
used[1] = True
cnt = 1

while stack:
    v = stack.pop()
    for to in g[v]:
        if not used[to]:
            used[to] = True
            cnt += 1
            stack.append(to)

print("YES" if cnt == n else "NO")