C++ में दी गई निर्भरता से कार्यों का क्रम ज्ञात करें

मान लीजिए कि हमारे पास अलग-अलग कार्य हैं; इन कार्यों को 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(), यह ग्राफ़, प्रारंभ, एक पथ पर, एक सरणी का दौरा किया, एक सरणी टोपोसॉर्ट,

  लेगा

• यदि विज़िट किया गया [प्रारंभ] चिह्नित है, तो -

  • झूठी वापसी

• ऑनपाथ [शुरू]:=सच, दौरा किया [शुरू]:=सच

• ग्राफ़ में प्रत्येक पड़ोसी के लिए[प्रारंभ], करें

  • यदि ऑनपथ [पड़ोसी] सत्य है या dfs (ग्राफ, पड़ोसी, ऑनपथ, विज़िट किया गया, टोपोसॉर्ट) सत्य है, तो -

    • सही लौटें

  • टोपोसॉर्ट के अंत में प्रारंभ डालें

• पथ पर लौटें [शुरू करें]:=झूठा

• मुख्य विधि से, निम्न कार्य करें -

• ग्राफ =पूर्व सरणी में संग्रहीत n कोने और किनारों के साथ ग्राफ बनाएं

• एक सरणी टोपोसॉर्ट परिभाषित करें

• आकार n के पथ पर एक सरणी परिभाषित करें और असत्य से भरें

• n आकार की देखी गई सरणी को परिभाषित करें और असत्य से भरें

• इनिशियलाइज़ i :=0 के लिए, जब i

  • यदि विज़िट किया गया [i] गलत है और dfs (ग्राफ, i, ऑनपाथ, विज़िट किया गया, टोपोसॉर्ट) सत्य है, तो -

    • रिक्त सरणी लौटाएं

• सरणी टोपोसॉर्ट को उलट दें

• टॉपोसॉर्ट पर लौटें

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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