এই নিবন্ধে, প্রদত্ত পূর্বশর্তের ভিত্তিতে প্রদত্ত সমস্ত কাজ শেষ করা সম্ভব কিনা তা পরীক্ষা করার জন্য আমরা একটি প্রোগ্রাম নিয়ে আলোচনা করব৷
উদাহরণস্বরূপ, আসুন আমরা বলি যে আমাদের তিনটি কাজ দেওয়া হয়েছে এবং পূর্বশর্ত হল [[1, 0], [2, 1], [3, 2]]।
( [1,0] এর অর্থ হল '1' টাস্ক নিতে; '0' টাস্কটি আগে শেষ করতে হবে।)
তারপরে, এই উদাহরণে যেহেতু '0' টাস্কের কোনো পূর্বশর্ত নেই এটি প্রথমে সম্পূর্ণ করা যেতে পারে। তারপর '1' টাস্কটি সম্পূর্ণ করা যেতে পারে, যেহেতু '0' টাস্কটি সম্পন্ন হয়েছে। একইভাবে, '2' এবং '3' উভয় কাজও সম্পন্ন করা যেতে পারে। সুতরাং এই ক্ষেত্রে উত্তর হবে "সত্য"৷
৷এই সমস্যাটি গ্রাফ অ্যালগরিদম ব্যবহার করে সমাধান করা যেতে পারে। যেহেতু, অ্যারেগুলি গ্রাফ অ্যালগরিদমের সাথে সুবিধাজনক নয়, আমরা এটিকে একটি গ্রাফে রূপান্তর করব। টাস্ক 'm' থেকে টাস্ক 'n' পর্যন্ত একটি প্রান্ত তৈরি করে এটি করা যেতে পারে, যদি টাস্ক 'n'-এর 'm' সমাপ্তি হিসাবে নির্ভরশীলতা থাকে।
গ্রাফ তৈরি হয়ে গেলে আমরা DFS ব্যবহার করতে পারি। এতে, আমরা একটি নির্দিষ্ট নোড থেকে শুরু করতে পারি এবং তারপর তার নিকটতম নোড এবং তারপর সেই নোডের নিকটতম নোড এবং আরও অনেক কিছুতে যেতে পারি। যদি আমরা একটি নোডের সম্মুখীন হই যা পূর্বে পরিদর্শন করা হয়েছে, একটি চক্র তৈরি করা হয় এবং আমরা "False" ফেরত দেব। অন্যথায়, একবার আমরা একটি টার্মিনালে পৌঁছালে, গ্রাফের সমস্ত নোড পরিদর্শন না করা পর্যন্ত এই প্যাটার্নটি আবার অন্য নোড দ্বারা অনুসরণ করা হবে। যদি সমস্ত নোড পৌঁছে যায়, আমরা "সত্য" ফেরত দেব।
উদাহরণ
#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
