# Find Eventual Safe States

• Why am I getting TLE on last few test cases. It uses DFS to find cycle.

``````class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
unordered_set<int> cycleNodes;
vector<int> safeNodes;
for(int i=0; i < graph.size(); i++) {
vector<bool> visited(graph.size(), false);
findCycles(i, graph, cycleNodes, visited);
}
for(int i=0; i<graph.size(); i++) {
if(cycleNodes.find(i) == cycleNodes.end()) {
safeNodes.push_back(i);
}
}
return safeNodes;
}

bool findCycles(int node, vector<vector<int>>& graph, unordered_set<int> &cycleNodes, vector<bool> &visited) {
if(cycleNodes.find(node) != cycleNodes.end()) {
return true;
}
if(visited[node] == true) {
cycleNodes.insert(node);
return true;
}
visited[node] = true;
for(int i=0; i<graph[node].size(); i++) {
bool isCycle = findCycles(graph[node][i], graph, cycleNodes, visited);
if(isCycle) {
cycleNodes.insert(node);
return true;
}
}
visited[node] = false;
return false;
}
};
``````

• @vigjadel It's probably due to below sloc. We should preserve the visited states to avoid doing redundant dfs. Try moving this line above for loop.

vector<bool> visited(graph.size(), false);

• Had to do 2 optimizations

1. visited array was getting created on every iteration
2. When node is black I can stop further computation.
``````class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
vector<int> color(graph.size(), 0);
vector<int> safeNodes;
for(int i=0; i < graph.size(); i++) {
findCycles(i, graph, color);
}
for(int i=0; i<graph.size(); i++) {
if(color[i] == 3) {
safeNodes.push_back(i);
}
}
return safeNodes;
}

bool findCycles(int node, vector<vector<int>>& graph, vector<int> &color) {
if(color[node] == 2) {
return true;
}
if(color[node] == 3) {
return false;
}
if(color[node] == 1) {
color[node] = 2;
return true;
}
color[node] = 1;
for(int i=0; i<graph[node].size(); i++) {
bool isCycle = findCycles(graph[node][i], graph, color);
if(isCycle) {
color[node] = 2;
return true;
}
}
color[node] = 3;
return false;
}
};
``````

• We can further optimize it by removing a redundant color

``````class Solution {
public:
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
vector<int> color(graph.size(), 0);
vector<int> safeNodes;
for(int i=0; i < graph.size(); i++) {
findCycles(i, graph, color);
}
for(int i=0; i<graph.size(); i++) {
if(color[i] == 2) {
safeNodes.push_back(i);
}
}
return safeNodes;
}

bool findCycles(int node, vector<vector<int>>& graph, vector<int> &color) {
if(color[node] == 2) {
return false;
}
if(color[node] == 1) {
return true;
}
color[node] = 1;
for(int i=0; i<graph[node].size(); i++) {
bool isCycle = findCycles(graph[node][i], graph, color);
if(isCycle) {
return true;
}
}
color[node] = 2;
return false;
}
};
``````

• Thanks for your excellent solution and explanation!

• here are my modified solution based on your explanation.

``````class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> res = new ArrayList<>();
if(graph == null || graph.length == 0)  return res;

int nodeCount = graph.length;
int[] color = new int[nodeCount];

for(int i = 0;i < nodeCount;i++){
}

return res;
}
public boolean dfs(int[][] graph, int start, int[] color){
if(color[start] != 0)   return color[start] == 1;

color[start] = 2;
for(int newNode : graph[start]){
if(!dfs(graph, newNode, color))    return false;
}
color[start] = 1;

return true;
}
}
``````

• In Approach #2, Why do we need to skip current iteration while traversing the neighbors ? I attempted the code without

``````if (color[node] == 2)
continue;
``````

and it got accepted

• @ATM-SALEH Because when the color of its neighbour is BLACK, we know it's been visited and it's safe(will lead to a terminal state). We don't have to do redundant dfs traversal.

• @awice, @raynow, @ATM-SALEH: so we should check the condition "color[nei] == 2" instead of the condition "color[node] == 2".

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.