hi, let Avik connect you.
** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.
** You can check all the posts on the Posts page.
** More about me in the About Me section.
Keys and Rooms
Problem: 841. Keys and Rooms
Problem Link: leetcode.com/problems/keys-and-rooms/
Approach:
From node 0, tried to check how many nodes I can visit.
For any source src, if there is any nodes in the list that are same as src then skipped taking that node into consideration.
Counted number of accessed node in total.
Returned the count.
Checked if the count becomes equal to the count of total rooms.
Returned true if it is, else returned false.
Time and Space Complexity:
Time Complexity: O(N)
Space Complexity: O(N)
Code [C++] : BFS
class Solution {
public:
int visit(int src, vector<vector<int>> & graph, vector<bool> & visited){
visited[src] = true;
queue<int>node_q; node_q.push(src);
int count = 1;
while(!node_q.empty()){
int top_node = node_q.front();
node_q.pop();
for(int i=0; i<graph[top_node].size(); i++){
int child = graph[top_node][i];
if(!visited[child] && child != top_node){
visited[child] = true;
count++;
node_q.push(child);
}
}
}
return count;
}
bool canVisitAllRooms(vector<vector<int>>& rooms) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = rooms.size();
vector<bool>visited(1001, false);
return visit(0, rooms, visited) == n;
}
};
Code [C++] : DFS
class Solution {
public:
int visit(int src, vector<vector<int>> & graph, vector<bool> & visited){
visited[src] = true;
int count = 1, child_sz = graph[src].size();
for(int i=0; i<child_sz; i++){
int next = graph[src][i];
if(!visited[next] && next != src){
count += visit(next, graph, visited);
}
}
return count;
}
bool canVisitAllRooms(vector<vector<int>>& rooms) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = rooms.size();
vector<bool>visited(1001, false);
return visit(0, rooms, visited) == n;
}
};