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

ในบทความนี้ เราจะพูดถึงโปรแกรมเพื่อตรวจสอบว่าสามารถทำงานที่กำหนดทั้งหมดให้เสร็จสิ้นโดยพิจารณาจากข้อกำหนดเบื้องต้นที่ให้มาได้หรือไม่

ตัวอย่างเช่น สมมติว่าเราได้รับงานสามงานและข้อกำหนดเบื้องต้นคือ [[1, 0], [2, 1], [3, 2]]

( [1,0] หมายถึงการรับภารกิจ '1' งาน '0' จะต้องทำให้เสร็จก่อน)

จากนั้น ในตัวอย่างนี้ เนื่องจากงาน '0' ไม่มีข้อกำหนดเบื้องต้นใดๆ จึงสามารถดำเนินการให้เสร็จสิ้นได้ก่อน จากนั้นงาน '1' จะเสร็จสิ้นได้ เนื่องจากงาน '0' เสร็จสิ้นแล้ว ในทำนองเดียวกัน งาน '2' และ '3' ก็สามารถทำได้เช่นกัน ดังนั้นคำตอบในกรณีนี้จะเป็น “จริง”

ปัญหานี้สามารถแก้ไขได้โดยใช้อัลกอริธึมกราฟ เนื่องจากอาร์เรย์ไม่สะดวกกับอัลกอริธึมกราฟ เราจะแปลงเป็นกราฟ ซึ่งสามารถทำได้โดยทำให้ขอบจากการพูดว่างาน 'm' เป็นงาน 'n' หากงาน 'n' มีการพึ่งพาเมื่อเสร็จสิ้น 'm'

เมื่อสร้างกราฟแล้ว เราก็สามารถใช้ DFS ได้ ในการนั้น เราสามารถเริ่มจากโหนดใดโหนดหนึ่ง จากนั้นไปที่โหนดที่ใกล้ที่สุด จากนั้นจึงไปที่โหนดที่ใกล้ที่สุดไปยังโหนดนั้นเป็นต้น หากเราพบโหนดที่เคยเยี่ยมชมก่อนหน้านี้ วงจรจะถูกสร้างขึ้นและเราจะคืนค่าเป็น "เท็จ" มิฉะนั้น เมื่อเราไปถึงเทอร์มินัล รูปแบบนี้จะถูกตามด้วยโหนดอื่นอีกครั้ง จนกว่าจะมีการเยี่ยมชมโหนดทั้งหมดในกราฟ หากถึงโหนดทั้งหมด เราจะคืนค่า "จริง"

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
// Converts list into graph
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;
}
//to check if all the nodes are visited
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;
}
//to check if all the tasks can be completed
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