หาลำดับงานจาก Dependency Graph (Topological Sort) ใน C++

Topological Sort สำหรับ Task Scheduling

กำหนด n งาน (0 ถึง n-1) และ Prerequisite pairs [u, v] หมายถึงต้องทำ v ก่อน u หาลำดับงานที่ถูกต้อง (Topological Order) หากมี Cycle ให้คืนอาร์เรย์ว่าง

อัลกอริทึม DFS + Cycle Detection

1. สร้าง Adjacency List จาก Prerequisites
2. DFS ทุกโหนดที่ยังไม่ได้เยี่ยม:
   • Mark onPath = True (สำหรับตรวจ Cycle)
   • ถ้าเจอเพื่อนบนที่ onPath = True → มี Cycle
   • DFS เพื่อนบนทั้งหมด
   • Push โหนดปัจจุบันเข้า toposort
   • Mark onPath = False
3. Reverse toposort ได้ลำดับที่ถูกต้อง

โค้ดตัวอย่าง C++

#include 
using namespace std;

vector> create_graph(int n, vector>& pre) {
    vector> graph(n);
    for (auto& p : pre)
        graph[p.second].insert(p.first);
    return graph;
}

bool dfs(vector>& graph, int start,
         vector& onpath, vector& visited, vector& toposort) {
    if (visited[start]) return false;
    onpath[start] = visited[start] = true;
    for (int neigh : graph[start])
        if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
            return true;
    toposort.push_back(start);
    return onpath[start] = false;
}

vector get_order(int n, vector>& pre) {
    auto graph = create_graph(n, pre);
    vector toposort;
    vector onpath(n, false), visited(n, false);
    for (int i = 0; i < n; i++)
        if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
            return {};
    reverse(toposort.begin(), toposort.end());
    return toposort;
}

int main() {
    int n = 4;
    vector> pre = {{1,0},{2,0},{3,2},{3,1},{4,0}};
    auto v = get_order(n, pre);
    for (int x : v) cout << x << ' ';  // 0 1 4 2 3
}