Задача: 841. Keys and Rooms
Сложность: medium

Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

👨‍💻 Алгоритм:

1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать.

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

3⃣Пока стек не пуст, извлекайте ключи из стека и используйте их для открытия новых комнат, добавляя найденные ключи в стек. Если все комнаты посещены, верните true, иначе false.

😎 Решение:

public class Solution {
    public bool CanVisitAllRooms(IList<IList<int>> rooms) {
        bool[] seen = new bool[rooms.Count];
        seen[0] = true;
        Stack<int> stack = new Stack<int>();
        stack.Push(0);

        while (stack.Count > 0) {
            int node = stack.Pop();
            foreach (int nei in rooms[node]) {
                if (!seen[nei]) {
                    seen[nei] = true;
                    stack.Push(nei);
                }
            }
        }

        foreach (bool v in seen) {
            if (!v) return false;
        }
        return true;
    }
}

Ставь 👍 и забирай 📚 Базу знаний