今天要寫拓撲排序~~
一個有向無環圖，必定存在一種(以上)的拓撲排序
定義：
將圖中所有點展開成序列，對任意節點u, v而言，若u出現在v的前面，說明圖中有u->v的通路
一樣找一題例題來解釋~~

例題&算法

802. 找到最终的安全状态
題目敘述：題目給一張圖，輸出有哪些起點，最後可以在有限步數走到終點(也就是無環)

[法一]拓撲排序

思路：

1. 先繪製一張反圖(方向相反)
2. 找出反圖入度為0的節點(原本圖的出度0)，這些節點是安全的(走到這一定無環了，因為原本的圖這些節點出度0，也就是終點)
3. 將這些節點放入queue中
4. 取出queue元素，與queue中節點相鄰的節點入度減一
5. 重複2->3->4
   最後入度為0的，都是安全的節點
   直接看程式碼~~

#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
#define mp make_pair
class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        //反圖&inDeg
        int n = graph.size();
        vt<int> inDeg(n);
        vt<int> res;
        iMat rg(n);
        for(int i = 0; i<n; ++i){
            inDeg[i] = graph[i].size();
            for(int j = 0; j<graph[i].size(); ++j){
                rg[graph[i][j]].pb(i);
            }
        }
        queue<int> q;
        //將所有入度=0的放入queue
        for(int i = 0; i<n; ++i){
            if(inDeg[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            vt<int> adj = rg[curr];
            for(int i = 0; i<adj.size(); ++i){
                inDeg[adj[i]]--;
                if(inDeg[adj[i]]==0){
                    q.push(adj[i]);
                }
            }
        }
        for(int i = 0; i<n; ++i){
            if(inDeg[i]==0){
                res.pb(i);
            }
        }
        return res;
    }
};

WHY?

反圖入度為0(原本的圖出度0)就代表這個節點是終點了，一定沒有辦法形成環，那走到這個節點的路一定也不會形成環，可以將這條邊去除(相鄰節點反圖入度-1)，最後入度為0的全部都是安全節點~~

[法二]標註DFS

就是DFS加上標註
標註出3種狀態

1. 未訪問
2. 訪問中
3. 已訪問(安全)

#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
#define mp make_pair
class Solution {
    vt<int> mark;
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        //[法一] 3種狀態DFS，可以算是記憶化搜索(?
        int n = graph.size();
        mark.resize(n);
        vt<int> res;
        for(auto& i:mark){
            mark[i] = 0; //未被訪問
        }
        for(int i = 0; i<n; ++i){
            if(dfs(graph, i)){
                res.pb(i);
            }
        }
        return res;
    }
    bool dfs(iMat& graph, int node){
        if(mark[node]!=0){
            return mark[node]==2;
        }
        vt<int> adj = graph[node];
        mark[node] = 1;
        for(auto e:adj){
            if(!dfs(graph, e)){
                return false;
            }
        }
        mark[node] = 2;
        return true;
    }
};