# LeetCode 802. Find Eventual Safe States

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

## 題目大意

給定一張 `n` 頂點之有向圖 `graph` ，其頂點編號 `0` - `n-1` ，定義：

- terminal node: 無射出邊的頂點
- safe node: 任一由該頂點出發之 path 最終皆止於 terminal node 或是另一個 safe node

以升序排列回傳所有 safe nodes

## 思考

這題個人覺得不錯，很能驗證圖論有沒有學好，我在[DSA Graph (1)](https://hackmd.io/@RyoukiWei/graph_1) 中介紹過 DFS
是的，這題我們可以使用 DFS 解題

該怎麼想呢？

最關鍵的問題是，那怎樣的頂點會是，我們說 unsafe node 呢？根據定義，代表說從它出發的 path 不會停在 terminal node 或是另一個 safe node，換句話說，它這 path 停不下來
這是什麼意思呢？這不就是在說這條 path 其實就是圖上的一個 cycle 嗎？

而且這個想法立刻就為我們帶來一個好處，因為 cycle 上任一點都能出發，然後繞圈停不下來，所以當你發現了一個 cycle ，這上面的所有頂點必然不是 safe node
找 cycle ？這我們可熟了，用 DFS 就好了啊

再來，terminal node 本身不會射出，這代表就不存在由它出發的 path
換句話說，terminal node 必然是 safe node
所以頂點不是屬於 safe node 就是不屬於 safe node

C++ 參考解答：

經過上面討論，我們知道我們對頂點的狀態只需要分成三種：

1. 尚未探索的
2. 正從它出發的
3. 確定是 safe 的

如果該頂點在 cycle 上，那我們從它出發，總有一天會走回原處，此時 `states[curr] != State::SAFE` ，就會回傳 `false`不給它標上 `State::SAFE`
並且這過程經過的頂點都不再是 `State::UNVISITED` 了，相當於這整個 cycle 上的頂點都能被立刻揪出不是 safe node

class Solution
{
public:
    vector<int> eventualSafeNodes(vector<vector<int>> &graph)
    {
        const int n = graph.size();
        vector<State> states(n, State::UNVISITED);
        vector<int> ans;
        ans.reserve(n);

        for (int i = 0; i < n; ++i)
        {
            if (dfs(graph, i, states))
                ans.push_back(i);
        }

        return ans;
    }

private:
    enum class State : char
    {
        UNVISITED,
        VISITING,
        SAFE,
    };

    bool dfs(const vector<vector<int>> &graph, int curr, vector<State> &states)
    {
        if (states[curr] != State::UNVISITED)
            return states[curr] == State::SAFE;

        states[curr] = State::VISITING;
        for (int neighbor : graph[curr])
        {
            if (!dfs(graph, neighbor, states))
                return false;
        }

        states[curr] = State::SAFE;
        return true;
    }
};

題目要求回傳順序要從小到大，因為節點編號就是 `0` - `n-1` ，所以用迴圈從 `0` 號開始確認就能得出所求

GO 參考解答：

func eventualSafeNodes(graph [][]int) []int {
	n := len(graph)
	states := make([]int8, n) // 0: unvisited, 1: visiting, 2: safe
	ans := make([]int, 0, n)

	var dfs func(int) bool
	dfs = func(node int) bool {
		if states[node] != 0 {
			return states[node] == 2
		}

		states[node] = 1
		for _, neighbor := range graph[node] {
			if !dfs(neighbor) {
				return false
			}
		}

		states[node] = 2
		return true
	}

	for i := 0; i < n; i++ {
		if dfs(i) {
			ans = append(ans, i)
		}
	}

	return ans
}