1. Идея

Есть несколько комнат с номерами от 0 до n - 1. Изначально открыта только комната 0.
В каждой комнате лежат ключи от некоторых других комнат. Нужно понять, можно ли, начиная из комнаты 0, попасть во все комнаты.

По сути это задача на обход графа:

• каждая комната — это вершина;
• ключ из комнаты u в комнату v — это ориентированное ребро u -> v.

Тогда задача сводится к вопросу:

достижимы ли все вершины из вершины 0?

Для этого достаточно выполнить обычный обход графа — DFS или BFS.

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

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

3. Не важно, в каком именно порядке обходить комнаты:

   • в глубину (DFS),
   • в ширину (BFS).

   Результат будет одинаковым: либо все достижимы, либо нет.

4. Чтобы не зациклиться, нужно хранить массив visited, где отмечаются уже посещённые комнаты.
5. В конце достаточно проверить, что количество посещённых комнат равно n.

3. Алгоритм

Рассмотрим решение через DFS.

1. Считываем число комнат n.
2. Создаём массив visited длины n, изначально все значения false.
3. Запускаем обход из комнаты 0.
4. Когда попадаем в комнату u:
   • отмечаем её как посещённую;
   • для каждого ключа v из rooms[u]:
     • если v ещё не посещена, рекурсивно обходим v.
5. После завершения обхода проверяем, все ли комнаты посещены.
   • если да, выводим YES;
   • иначе выводим NO.

Можно также реализовать через стек или очередь, чтобы избежать рекурсии. Но сама идея остаётся той же.

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

Докажем корректность.

Обозначим через достижимые комнаты те, в которые можно попасть из комнаты 0, используя найденные по пути ключи.

Что делает DFS

DFS начинает с комнаты 0 и переходит по всем ключам из каждой посещённой комнаты.
То есть если из комнаты u есть ключ в v, и мы уже можем попасть в u, то DFS тоже сможет перейти в v.

Значит:

• каждая комната, которую посетил DFS, действительно достижима;
• каждая достижимая комната рано или поздно будет посещена DFS.

Почему не пропустим достижимую комнату

Рассмотрим любую достижимую комнату x.
Раз она достижима, существует цепочка переходов:

0 -> a1 -> a2 -> ... -> x

DFS стартует из 0, затем рассмотрит все ключи из 0, потом из достижимых через них комнат и так далее.
Значит, он сможет пройти по всей этой цепочке и в итоге посетит x.

Почему ответ верный

• Если после обхода все комнаты посещены, значит все комнаты достижимы из 0, ответ YES.
• Если осталась хотя бы одна непосещённая комната, то пути из 0 к ней нет, иначе DFS обязательно бы до неё дошёл. Тогда ответ NO.

Следовательно, алгоритм работает правильно.

5. Сложность

Пусть:

• n — число комнат;
• m — общее число всех ключей во всех комнатах.

Тогда:

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

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

• по времени: O(n + m)
• по памяти: O(n) для массива посещений
  (и ещё до O(n) на стек рекурсии или явный стек при итеративной реализации).

CPP

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

    int n;
    cin >> n;

    vector<vector<int>> rooms(n);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        rooms[i].resize(k);
        for (int j = 0; j < k; ++j) {
            cin >> rooms[i][j];
        }
    }

    vector<bool> visited(n, false);
    stack<int> st;
    st.push(0);
    visited[0] = true;

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

        for (int to : rooms[v]) {
            if (to >= 0 && to < n && !visited[to]) {
                visited[to] = true;
                st.push(to);
            }
        }
    }

    bool ok = true;
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            ok = false;
            break;
        }
    }

    cout << (ok ? "YES" : "NO") << '\n';
    return 0;
}

PYTHON

import sys


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    rooms = []

    for _ in range(n):
        k = int(next(it))
        cur = [int(next(it)) for _ in range(k)]
        rooms.append(cur)

    visited = [False] * n
    stack = [0]
    visited[0] = True

    while stack:
        v = stack.pop()
        for to in rooms[v]:
            if 0 <= to < n and not visited[to]:
                visited[to] = True
                stack.append(to)

    print("YES" if all(visited) else "NO")


if __name__ == "__main__":
    main()