Tìm thứ tự thực hiện nhiệm vụ từ các phụ thuộc đã cho trong C++

Cho n nhiệm vụ (0 đến n-1). Một số nhiệm vụ có điều kiện tiên quyết, ví dụ: muốn làm nhiệm vụ 2 phải hoàn thành nhiệm vụ 1 trước, biểu diễn bằng cặp [2, 1]. Cho số nhiệm vụ và danh sách các cặp phụ thuộc, tìm thứ tự thực hiện để hoàn thành tất cả. Nếu có nhiều thứ tự đúng, trả về một trong số đó. Nếu không thể hoàn thành tất cả, trả về mảng rỗng.

Ví dụ: n = 4, A = [[1,0],[2,0],[3,2],[3,1],[4,2]] -> kết quả [0, 2, 1, 4, 3].

Thuật toán giải quyết (Topological Sort - DFS)

• Xây dựng đồ thị từ danh sách phụ thuộc.
• Dùng DFS để phát hiện chu trình và sắp xếp topo:
  • Mảng visited, onpath, toposort.
  • Hàm dfs: nếu visited[start] trả về false; đánh dấu onpath và visited; duyệt các đỉnh kề, nếu onpath[neigh] hoặc dfs trả về true -> có chu trình -> trả về true; push start vào toposort; gỡ onpath[start].
• Gọi dfs cho mọi đỉnh chưa thăm. Nếu phát hiện chu trình trả về mảng rỗng.
• Đảo ngược toposort và trả về.

Ví dụ minh họa (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) {
    vector> 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}};
    vector v = get_order(n, pre);
    for (int x : v) cout << x << " ";
}

Đầu vào

4, {{1,0},{2,0},{3,2},{3,1},{4,0}}

Đầu ra

0 1 4 2 3