Kiểm tra hoàn thành được tất cả task theo phụ thuộc C++

Cho N task và các cặp phụ thuộc [u, v] nghĩa là task v phải làm trước task u. Kiểm tra có thể hoàn thành tất cả task không (tức là đồ thị không có chu trình).

Giải pháp: Topological Sort / DFS phát hiện chu trình

• Xây đồ thị hướng: v → u (v phải làm trước u).
• DFS với 3 trạng thái: 0=chưa thăm, 1=đang thăm (trong stack), 2=đã xong.
• Gặp trạng thái 1 → có chu trình → false.

Chương trình C++

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

bool canFinish(int n, vector>& deps) {
    vector> adj(n);
    for (auto &p : deps) adj[p.second].push_back(p.first);
    
    vector state(n, 0); // 0=unvisited, 1=visiting, 2=done
    function dfs = [&](int u) {
        state[u] = 1;
        for (int v : adj[u]) {
            if (state[v] == 1) return true; // cycle
            if (state[v] == 0 && dfs(v)) return true;
        }
        state[u] = 2;
        return false;
    };
    
    for (int i = 0; i < n; i++)
        if (state[i] == 0 && dfs(i)) return false;
    return true;
}

int main() {
    int tasks = 6;
    vector> deps = {{1,0}, {2,1}, {3,2}, {5,3}, {4,5}};
    cout << (canFinish(tasks, deps) ? "True" : "False") << "\n";
    return 0;
}

Kết quả

True