इस लेख में, हम यह जांचने के लिए एक कार्यक्रम पर चर्चा करेंगे कि क्या दिए गए सभी कार्यों को दिए गए पूर्वापेक्षाओं के आधार पर पूरा करना संभव है।
उदाहरण के लिए, मान लें कि हमें तीन कार्य दिए गए हैं और पूर्वापेक्षाएँ हैं [[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