//
// Created by YUQIONG LI on 16/9/2018.
//
#include <vector>
#include <stack>
using std::vector;
using std::stack;
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
int numRooms = rooms.size();
vector<int> res;
stack<int> s;
s.push(0);
vector<int> visited;
while (!s.empty()){
// try a postorder
int curr = s.top();
// 1. Put all unvisited children onto the stack.
int unvisited_children = 0;
for (int & child : rooms[curr]){
if (std::find(visited.begin(), visited.end(), child) != visited.end()){
// this child has been visited. Do nothing about it.
continue;
}
else{
s.push(child);
unvisited_children++;
}
}
// 2. Check what we do with this node.
// If no unvisited child, we print this node, remove it from the stack
if (unvisited_children == 0){
res.push_back(curr);
s.pop();
}
// Else, we visit one of its children
else{
continue; // go back to the while loop
}
}
return res.size() == rooms.size();
}
};
int main(){
vector< vector<int> > rooms = {{1,3},{3,0,1},{2},{0}};
Solution s;
return s.canVisitAllRooms(rooms);
}
Wrong solution.
1. With a tree there is only one direction. But with a graph, a node can be both parent and child of another node. So this has an infinite loop in the code.
1. With a tree there is only one direction. But with a graph, a node can be both parent and child of another node. So this has an infinite loop in the code.
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.