โปรแกรม C++ ตรวจสอบว่าสามารถทำภารกิจทั้งหมดเสร็จได้หรือไม่จากข้อกำหนดก่อนหน้า

ตรวจสอบว่าสามารถทำภารกิจ (tasks) ทั้งหมดเสร็จได้หรือไม่ ตามเงื่อนไขก่อนหน้า (prerequisites)

ตัวอย่าง: 3 ภารกิจ prerequisites = [[1,0], [2,1], [3,2]] หมายถึง ต้องทำ 0 ก่อนถึงทำ 1 ได้, ทำ 1 ก่อนถึงทำ 2 ได้...

แก้ด้วย Graph + DFS: สร้างกราฟจาก dependencies (edge จาก m ไป n ถ้า n ต้องการ m) DFS ตรวจจับ cycle ถ้ามี cycle = False ไม่มี cycle และถึงทุกโหนด = True

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

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

vector<unordered_set<int>> make_graph(int Tasks, vector<pair<int,int>>& dependencies) {
    vector<unordered_set<int>> graph(Tasks);
    for (auto pre : dependencies) graph[pre.second].insert(pre.first);
    return graph;
}

bool cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onway, vector<bool>& visited) {
    if (visited[node]) return false;
    onway[node] = visited[node] = true;
    for (int near : graph[node]) {
        if (onway[near] || cycle(graph, near, onway, visited)) return true;
    }
    return onway[node] = false;
}

bool canFinish(int Tasks, vector<pair<int,int>>& dependencies) {
    vector<unordered_set<int>> graph = make_graph(Tasks, dependencies);
    vector<bool> onway(Tasks, false), visited(Tasks, false);
    for (int i = 0; i < Tasks; i++)
        if (!visited[i] && cycle(graph, i, onway, visited)) return false;
    return true;
}

int main() {
    int Tasks = 6;
    vector<pair<int,int>> dependencies;
    dependencies.push_back(make_pair(1,0));
    dependencies.push_back(make_pair(2,1));
    dependencies.push_back(make_pair(3,2));
    dependencies.push_back(make_pair(5,3));
    dependencies.push_back(make_pair(4,5));
    if (canFinish(Tasks, dependencies)) cout << "True";
    else cout << "False";
    return 0;
}

ผลลัพธ์

True