C++ এ প্রদত্ত নির্ভরতা থেকে কাজের ক্রম খুঁজুন

ধরুন আমাদের n বিভিন্ন কাজ আছে; এই কাজ 0 থেকে n-1 লেবেল করা হয়. কিছু কাজের পূর্বপ্রস্তুতি কাজ থাকতে পারে, তাই উদাহরণ হিসেবে যদি আমরা টাস্ক 2 বেছে নিতে চাই তাহলে আমাদের প্রথমে টাস্ক 1 শেষ করতে হবে, যা একটি জোড়া হিসাবে উপস্থাপন করা হয় - [2, 1] যদি আমাদের কাছে মোট কাজের সংখ্যা এবং একটি তালিকা থাকে পূর্বশর্ত জোড়ার, আমাদের সমস্ত কাজ শেষ করার জন্য কাজের ক্রম খুঁজে বের করতে হবে। যদি একাধিক সঠিক আদেশ থাকে তবে আমরা তাদের মধ্যে একটি ফেরত দিতে পারি। এবং যদি সমস্ত প্রদত্ত কাজ শেষ করা অসম্ভব হয়, তাহলে একটি খালি অ্যারে ফেরত দিন৷

সুতরাং, যদি ইনপুট n =4, এবং A =[[1, 0], [2, 0], [3, 2], [3, 1], [4,2]] এর মত হয়, তাহলে আউটপুট হবে হতে [0, 2, 1, 4, 3]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন, এটি গ্রাফ, শুরু, একটি অনপথ, একটি অ্যারে পরিদর্শন করা, একটি অ্যারে টপোসর্ট,

• যদি পরিদর্শন করা হয় [শুরু] চিহ্নিত করা হয়, তাহলে −

  • মিথ্যা ফেরত দিন

• onpath[start] :=সত্য, পরিদর্শন করা [শুরু] :=সত্য

• গ্রাফে প্রতিটি প্রতিবেশীর জন্য [শুরু], করুন

  • যদি onpath[প্রতিবেশী] সত্য হয় বা dfs(গ্রাফ, প্রতিবেশী, অনপথ, পরিদর্শন করা, টপোসর্ট) সত্য হয়, তাহলে -

    • প্রত্যাবর্তন সত্য

  • toposort শেষে শুরু সন্নিবেশ করুন

• অনপথ [শুরু] ফেরত :=মিথ্যা

• মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• গ্রাফ =প্রাক অ্যারেতে সংরক্ষিত n শীর্ষবিন্দু এবং প্রান্ত দিয়ে গ্রাফ তৈরি করুন

• একটি অ্যারে টপোসর্ট সংজ্ঞায়িত করুন

• n আকারের একটি অ্যারে অনপাথ সংজ্ঞায়িত করুন এবং মিথ্যা

  দিয়ে পূরণ করুন

• n আকারের পরিদর্শন করা অ্যারে সংজ্ঞায়িত করুন এবং মিথ্যা

  দিয়ে পূরণ করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • যদি পরিদর্শন করা [i] মিথ্যা হয় এবং dfs(graph, i, onpath, visited, toposort) সত্য হয়, তাহলে -

    • ফাঁকা অ্যারে ফেরত দিন

• অ্যারে টপোসর্টকে বিপরীত করুন

• প্রত্যাবর্তন toposort

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;
vector<unordered_set<int> > create_graph(int n, vector<pair<int, int> >& pre) {
   vector<unordered_set<int> > graph(n);
   for (auto pre : pre)
      graph[pre.second].insert(pre.first);
   return graph;
}
bool dfs(vector<unordered_set<int> >& graph, int start,vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) {
   if (visited[start])
      return false;
   onpath[start] = visited[start] = true;
   for (int neigh : graph[start])
      if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
         return true;
   toposort.push_back(start);
   return onpath[start] = false;
}
vector<int> get_order(int n, vector<pair<int, int> > &pre){
   vector<unordered_set<int> > graph = create_graph(n, pre);
   vector<int> toposort;
   vector<bool> onpath(n, false), visited(n, false);
   for (int i = 0; i < n; i++)
      if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
         return {};
   reverse(toposort.begin(), toposort.end());
   return toposort;
}
int main() {
   int n = 4;
   vector<pair<int, int> > pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}};
   vector<int> v = get_order(n, pre);
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << " ";
   }
}

ইনপুট

4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}

আউটপুট

0 1 4 2 3