1. Идея

Каждую комнату удобно рассматривать как вершину графа.

Если в комнате i лежит ключ от комнаты j, это значит, что из вершины i можно перейти в вершину j.

Тогда задача сводится к простой проверке: достижимы ли все вершины графа из вершины 0.

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

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

1. Изначально доступна только комната 0.
2. Попав в комнату, мы сразу можем забрать все ключи из неё.
3. Если у нас появился ключ от новой комнаты, мы можем посетить её позже.
4. Нет смысла заходить в одну и ту же комнату несколько раз, поэтому нужно хранить массив visited.
5. Если после обхода количество посещённых комнат равно n, то все комнаты достижимы. Иначе — нет.

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

3. Алгоритм

1. Считываем n.
2. Считываем для каждой комнаты список ключей, лежащих в ней.
3. Создаём массив visited размера n, изначально везде false.
4. Создаём стек для обхода.
5. Помещаем в стек комнату 0, помечаем её как посещённую.
6. Пока стек не пуст:
   • извлекаем очередную комнату v;
   • перебираем все комнаты to, ключи от которых лежат в v;
   • если to ещё не посещена, помечаем её и добавляем в стек.
7. Считаем, сколько комнат удалось посетить.
8. Если посещено ровно n комнат, выводим true, иначе false.

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

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

Когда мы извлекаем из стека некоторую комнату v, это означает, что до неё уже можно добраться, начиная из комнаты 0.

Дальше мы рассматриваем все ключи, лежащие в v. Каждый такой ключ открывает некоторую комнату to. Значит, если мы уже умеем попасть в v, то после посещения v можем получить доступ и к to. Поэтому добавление to в стек корректно.

Таким образом, алгоритм постепенно находит все комнаты, в которые можно попасть по цепочке:

• стартуем из 0,
• из неё получаем ключи,
• идём в новые комнаты,
• там берём новые ключи,
• и так далее.

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

Если некоторая комната достижима из 0, существует последовательность комнат, по которой можно последовательно получать нужные ключи. Алгоритм обходит все такие переходы из уже достижимых комнат, поэтому рано или поздно доберётся и до этой комнаты.

Почему достаточно проверить cnt == n?

• Если cnt == n, значит, все комнаты были найдены обходом, то есть все достижимы из 0.
• Если cnt < n, значит, остались комнаты, до которых алгоритм добраться не смог. Следовательно, получить к ним доступ из 0 невозможно.

Значит, ответ алгоритма верный.

5. Сложность

Пусть суммарное количество ключей во всех комнатах равно m.

Тогда:

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

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

• по времени: O(n + m)
• по памяти: O(n + m)

С учётом ограничений это работает быстро.

6. Код на C++17

#include <iostream>
#include <vector>

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<char> visited(n, false);
    vector<int> st;
    st.push_back(0);
    visited[0] = true;
    int cnt = 1;

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

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

    cout << (cnt == n ? "true" : "false") << '\n';
    return 0;
}

7. Код на Python 3

import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    ptr = 0
    n = data[ptr]
    ptr += 1

    rooms = []
    for _ in range(n):
        k = data[ptr]
        ptr += 1
        rooms.append(data[ptr:ptr + k])
        ptr += k

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

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

    sys.stdout.write("true\n" if count == n else "false\n")


if __name__ == "__main__":
    main()