Leetcode 820 Solution

This article provides solution to leetcode question 820 (find-eventual-safe-states)
Categories:
Tags:
Access this page by simply typing in "lcs 820" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/find-eventual-safe-states

Solution

#define PENDING 1
#define SAFE_NODE 2
#define UNSAFE_NODE 3

class Solution {
    vector<int> nodes;

public:
    bool decide_safe(const vector<vector<int>>& graph, int i)
    {
        if (nodes[i] == SAFE_NODE)
            return true;

        if (nodes[i] == PENDING || nodes[i] == UNSAFE_NODE)
            return false;

        nodes[i] = PENDING;

        bool all_safe = true;
        for (auto dest : graph[i])
            all_safe &= decide_safe(graph, dest);

        nodes[i] = all_safe ? SAFE_NODE : UNSAFE_NODE;
        return all_safe;
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> ans;
        if (graph.empty())
            return ans;

        nodes.resize(graph.size());

        for (int i = 0; i < graph.size(); i++)
        {
            decide_safe(graph, i);

            if (nodes[i] == SAFE_NODE)
                ans.push_back(i);
        }

        return ans;
    }
};