---
# System prepended metadata

title: Algo｜Topological sort 拓樸排序
tags: [Algo]

---

# Topological sort 拓樸排序
- 若是有邊 a 指向 b，表示完成 a 之前必須要先完成 b
- 使用 dfs，依照結束順序得到一個序列
    ```clike=
    bool done[1000];
    vector<int> finish;

    void dfs(int id, vector<vector<int>> &G){
        done[id] = true;
        for(auto &nb:G[id])
            if(done[nb]==false)
                dfs(nb, G)
        finish.push_back(id);
    }

    void topologicalSort(vector<vector<int>> &G){
        for(int i=0;i<G.size();i++)
            if(done[i]==false)
                dfs(i, G);
    }
    ```

