There are n rooms labeled from 0 to n - 1&nbsp;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.

&nbsp;
Example 1:

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.


Example 2:

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.


&nbsp;
Constraints:


	n == rooms.length
	2 &lt;= n &lt;= 1000
	0 &lt;= rooms[i].length &lt;= 1000
	1 &lt;= sum(rooms[i].length) &lt;= 3000
	0 &lt;= rooms[i][j] &lt; n
	All the values of rooms[i] are unique.


class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        # Create a set of for rooms visited
        visited_rooms = set()
        
        # Create a queue to do a breadth first search visiting rooms
        # Append the first room, 0, to the queue to begin the search
        queue = collections.deque()
        queue.append(0)
        
        # Perform the breadth first search with the queue
        while queue:
            for _ in range(0, len(queue)):
                # Search the room
                room_number = queue.popleft()
                
                # If we haven't visited the room, get the keys from the room
                if room_number not in visited_rooms:
                
                    # Collect the keys from the room
                    found_keys = rooms[room_number]
                    
                    # Add the keys to the queue so they can be tested
                    for key in found_keys:
                        queue.append(key)
                        
                    # Add the current room to the visited set
                    visited_rooms.add(room_number)
        
        # If we visited all of the rooms, then the number of visited rooms should be
        # equal to the number of total rooms
        if len(visited_rooms) == len(rooms):
            return True
        
        return False
class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    		 boolean[] visited = new boolean[rooms.size()];
    		 visited[0]= true;
    		 for(int a:rooms.get(0))
    		 {
    			 if(!visited[a])
    			 {
    				 bfs(a, visited, rooms.size()-1, rooms);
    				 
    			 }
    		 }
    		 //System.out.println("arr -->>"+Arrays.toString(visited));
    		for(boolean a:visited)
    		{
    			if(!a)
    				return false;
    		}
    	      return true;
    	        
    	    }
    	 public void bfs(int key, boolean[] vivsted, int target,List<List<Integer>> rooms)
    	 {
    		
    		
    		 vivsted[key] = true;
    		 for(int a:rooms.get(key))
    		 {
    			 if(!vivsted[a])
    			 {
    				 bfs(a, vivsted, target, rooms);
    			 }
    		 }
    		 
    		 
    		
    	 }
       
}
class Solution {
public:
    void dfs(int node, vector<vector<int>>& rooms,vector<int> &visited){
        visited[node]=1;
        
        for(auto it: rooms[node]){
            if(visited[it]==0)
                dfs(it, rooms, visited);
            else continue;
        }
        return;
    }
    
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n=rooms.size();
        vector<int> visited(n,0);
        
        dfs(0,rooms,visited);
        
        for(int i=0;i<n;i++){
            if(visited[i]==0) return false;
        }    
        return true;
    }
};
function dfs(current,all,visited){
    if(visited.size==all.length){
        return true;
    }
    for(let i=0;i<all[current].length;i++){
        if(!visited.has(all[current][i])){
            visited.add(all[current][i]);
            if(dfs(all[current][i],all,visited))
                return true;
        }

    }
    return false;

}
var canVisitAllRooms = function(rooms) {
    let visited=new Set();
    visited.add(0);
    if (dfs(0,rooms,visited)) return true;
    return false;
};
Keys and Rooms