https://leetcode.com/problems/find-eventual-safe-states/description/
class Solution {
public:
vector<bool> visited;
vector<int> mem; // -1 unknown, 0 unsafe, 1 safe.
int n;
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
n = graph.size();
mem = vector<int>(n, -1);
visited = vector<bool>(n, false);
for (int i = 0; i < n; i++)
dfs(graph, i);
vector<int> res;
for (int i = 0; i < n; i++)
if (mem[i] == 1)
res.push_back(i);
return res;
}
bool dfs(vector<vector<int>>& graph, int i) {
// check if i is evetually safe
if (mem[i] != -1) return mem[i] == 1;
bool res = true;
if (visited[i]) { // A loop
res = false;
}
else {
visited[i] = true;
for (auto j : graph[i]) {
if (!dfs(graph, j)) {
res = false;
break;
}
}
// visited[i] = false; // This line is optional, since we've cached the result for i in mem.
}
mem[i] = res;
return res;
}
};