# Find Eventual Safe States

Dec 20, 2019

bool check(vector<vector<int>>& graph, vector<bool> &color, int i) {
for(auto &j: graph[i]) {
if (!color[j]) return false;
}
return true;
}
vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
int size = graph.size();
vector<int> res;
if (size == 0) return res;

vector<bool> color(size, false);
bool change = false;
for(int i = 0;i < size; i++)
if (graph[i].size() == 0) {
color[i] = true;
change = true;
}

while(change) {
change = false;
for(int i = 0;i < size; i++) {
if (color[i] == false && check(graph, color, i)) {
color[i] = true;
change = true;
}
}
}

for(int i = 0;i < size; i++) {
if (color[i]) res.push_back(i);
}
return res;
}


• 0：未访问（初始状态）
• 1：访问中
• 2：访问完成（安全状态）
• 3：在环中（不安全状态）

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
int size = graph.size();
vector<int> res;
if (size == 0) return res;

vector<int> color(size, 0); // 0 mean unvisit
for(int i = 0;i < size; i++) {
if (color[i] == 0) dfs(graph, color, i);
}

for(int i = 0;i < size; i++) {
if (color[i] == 2) res.push_back(i);
}
return res;

}

int dfs(vector<vector<int>> &graph, vector<int> &color, int node) {
// cout << "visit" << node << endl;
color[node] = 1; // in dfs
for(int j = 0;j < graph[node].size(); j++) {
int i = graph[node][j];
if ( (color[i] == 0 && dfs(graph, color, i) == 3) ||
color[i] == 1 || color[i] == 3
) {
color[node] = 3;
return 3;
}
}
color[node] = 2;// safe node
return color[node];
}

LeetCodeLeetCode

Binary Search Tree to Greater Sum Tree

Flatten a Multilevel Doubly Linked List

comments powered by Disqus