[Google][LeetCode] Keys and Rooms

Problem: There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.

When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.

Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.

Example:

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.

Input: rooms = [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.

Approach: If we look at this problem closely, we will come to know the given array is kind of a graph where one node is connected to another node (room) if it has key to that room so we just need to DFS on this graph and check if the number of visited nodes are equal to the number of rooms. If yes, return true; false otherwise.

Implementation in C#:

    public bool CanVisitAllRooms(IList<IList<int>> rooms)

    {

        int numOfRooms = rooms?.Count ?? 0;

        if (numOfRooms <= 1)

        {

            return true;

        }

        HashSet<int> visitedRooms = new HashSet<int>();

        this.CanVisitAllRoomsDFS(rooms, 0, visitedRooms);

        return visitedRooms.Count == numOfRooms;

    }

    private void CanVisitAllRoomsDFS(IList<IList<int>> rooms,

                                     int currRoom,

                                     HashSet<int> visitedRooms)

    {

        if (visitedRooms.Contains(currRoom))

        {

            return;

        }

        visitedRooms.Add(currRoom);

        IList<int> neighbourRooms = rooms[currRoom];

        foreach (int room in neighbourRooms)

        {

            this.CanVisitAllRoomsDFS(rooms, room, visitedRooms);

        }

    }

Complexity: O(n)