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() फ़ंक्शन परिभाषित करें, जो graph, start, onpath, visited सरणी, toposort सरणी लेता है।
• यदि visited[start] चिह्नित है, तो false लौटाएं।
• onpath[start] := true, visited[start] := true
• graph[start] में प्रत्येक neighbor के लिए:
  • यदि onpath[neighbor] true है या dfs(graph, neighbor, onpath, visited, toposort) true है, तो true लौटाएं।
• start को toposort के अंत में डालें।
• onpath[start] := false लौटाएं।
• मुख्य विधि से:
  • graph = create_graph(n, pre) (n शीर्ष और pre सरणी में संग्रहीत एज के साथ ग्राफ बनाएं)
  • toposort सरणी परिभाषित करें।
  • onpath सरणी आकार n false से भरें।
  • visited सरणी आकार n false से भरें।
  • i := 0 से n-1 तक:
    • यदि visited[i] false है और dfs(graph, i, onpath, visited, toposort) true है, तो खाली सरणी लौटाएं।
  • toposort सरणी को उल्टा करें।
  • toposort लौटाएं।

उदाहरण

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

#include 
using namespace std;

vector> create_graph(int n, vector>& pre) {
    vector> graph(n);
    for (auto p : pre)
        graph[p.second].insert(p.first);
    return graph;
}

bool dfs(vector>& graph, int start,
         vector& onpath, vector& visited, vector& 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 get_order(int n, vector>& pre) {
    vector> graph = create_graph(n, pre);
    vector toposort;
    vector 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> pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1}, {4, 0}};
    vector 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