# 802. Find Eventual Safe States
## 想法
若從 u 出發不會走到環上，則 u 是 safe node
證明:
從 u 出發不會走到環上 -> 每條從 u 為起點的路，一定是有限長度的，並且會走到 terminal node -> u 是 safe node
## 演算法(DFS)

dfs(adj, u, visited, inCycle):
    visited[u] = 1
    
    for every u's neighbor v:
        if visited[v] == 0:
            inCycle[u] = inCycle[u] or dfs(adj, v, visited, inCycle)
        else if visited[v] == 1:
            inCycle[u] = 1
            return 1
        else:
            inCycle[u] = inCycle[u] or inCycle[v]

    visited[u] = 2
    return inCycle[u]

main():
    建構圖
    宣告所需變數
    for every u in V:
        if !visited[u]:
            dfs(adj, u, visited, inCycle)
    ans = []
    將所有inCycle[u] == 0的u加入ans
    回傳ans

## 程式碼(DFS)

class Solution {
public:
    bool dfs(vector<vector<int>> &adj, int u, vector<int> &color, vector<bool> &inCycle) {
        color[u] = 1;
        for (auto it = adj[u].begin(); it != adj[u].end(); it++) {
            int v = *it;
            if (color[v] == 0) {
                inCycle[u] = inCycle[u] or dfs(adj, v, color, inCycle);
            } else if (color[v] == 1) {
                inCycle[u] = 1;
                return 1;
            } else {
                inCycle[u] = inCycle[u] or inCycle[v];
            }
        }
        color[u] = 2;
        return inCycle[u];
    }
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> adj(n, vector<int>());
        for (int u = 0; u < n; u++) {
            for (int v : graph[u]) {
                adj[u].push_back(v);
            }
        }
        vector<int> color(n);
        vector<bool> inCycle(n);
        for (int u = 0; u < n; u++) {
            if (!color[u]) {
                dfs(adj, u, color, inCycle);
            }
        }
        vector<int> ans;
        for (int u = 0; u < n; u++) {
            if (!inCycle[u]) {
                ans.push_back(u);
            }
        }
        return ans;
    }
};

## 演算法(BFS)

建構圖 G=(V,E)
建構反向圖 G'=(V,E')
對 G' 做拓樸排序 將過程中曾經進入 queue 的點放到 ans，ans 即為答案

### 正確性與完備性證明

#### 正確性
定理:若 u 曾經進入 queue 則 u 是 safe node

證明:使用循環不變式
- ```初始```:拓樸排序一開始將 indeg 為 0 的點推入 queue，因為是反向圖，所以在原圖中是 outdeg 為 0 的點，故它是 safe node。
- ```維持```:過程中每拿出一個點 u，對於 u 的所有鄰居 v，移除 (u,v) 邊，若 indeg[v] == 0，則 v 會被推入 queue，根據歸納假設， u 是 safe node，如果移除 (u,v) 會使得 v 的 indeg 變為 0，說明在原圖中 v 只會抵達 safe node，根據定義，v 也是 safe node。
- ```終止```:當 queue 為空時，根據歸納假設，已經找到所有曾經進入 queue 的點，故 ans 裡的值都是 safe node。

#### 完備性
定理:若 u 是 safe node，則 u 會進入 queue

證明:若 u 是 safe node，那 u 可達 terminal node，並且 u 到 terminal 必存在一條最長路徑。我們聲明，對於每個 u ，u 到 terminal node 最長路徑為 k，則 u 一定會進入 queue。
- 使用歸納法，在初始情況，我們不會漏掉任何最長 0 步到 terminal node 的節點，也就是說他們都會進入 queue，成立；假設最長 k - 1 步到 terminal node 的節點都成立，即最長 k - 1 步到 terminal node 的節點都會進入 queue；則對於最長 k 步到 terminal node 的節點 v，因為 v 到 terminal node 最長只需要 k 步，在演算法移除所有最長 k - 1 步以內到 terminal node 的節點的所有出邊後，indeg[v] == 0，故 v 也會被推入 queue，成立；故根據歸納法，若 u 是 safe node，則 u 會進入 queue，證明完成。

## 程式碼(BFS)

class Solution {
public:
    
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<vector<int>> adj(n);
        vector<int> indeg(n);
        for (int u = 0; u < n; u++) {
            for (int &v : graph[u]) {
                adj[v].push_back(u);
                indeg[u]++;
            }
        }
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (!indeg[i]) {
                q.push(i);
            }
        }

        vector<int> ans;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            ans.push_back(u);
            for (int &v : adj[u]) {
                if (--indeg[v] == 0) {
                    q.push(v);
                }
            }
        }
        sort(begin(ans), end(ans));
        return ans;
    }
};