# 拓樸排序

* 建立DAG的順序

1. 建立一個陣列儲存每個點連進去的邊的個數，以及儲存排序的佇列。
3. 從邊數為0的點開始，把點加入佇列，並把連到的點的邊數都減一(aka把那一點的邊都刪掉)。
4. 每次找邊數為0且沒用過的點開始，重複上一步驟。
6. 直到全部點都用過。
* 如果dag的排序中未包含所有點，代表圖不是dag，因為有些點在刪除其他點後的入邊數還不是0
* $O(v+e)$

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;// n: 點個數 m:邊個數
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>());
    vector<int> cnt(n, 0);
    int a, b;
    for(int i=0;i<m;++i){
        cin >> a >> b;
        graph[a].push_back(b);
        cnt[b]++;
    }
    // find the node with no edge
    queue<int> topo;
    for(int i=0;i<n;++i)
        if(cnt[i]==0)
            topo.push(i);

    vector<int> ans;
    while(!topo.empty()){
        int v=topo.front();
        topo.pop();
        ans.push_back(v);

        for(int a:graph[v]){
            cnt[a]--;
            if(cnt[a]==0)
                topo.push(a);
        }
    }
}

dag最短路徑
---

* 從第一個位置開始，比對它所連到位置其路徑長（or加權重）是否為最小，aka. dp[j]=min(dp[j], dp[i]+weight[j]), j為i連到的地方，weight[i]為邊的權重。