Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: जांचें कि क्या दिए गए निर्भरताओं से सभी कार्यों को पूरा करना संभव है


इस लेख में, हम एक प्रोग्राम पर चर्चा करेंगे जो दिए गए पूर्वापेक्षाओं के आधार पर सभी दिए गए कार्यों को पूरा करना संभव है या नहीं जांचता है।

उदाहरण के लिए, मान लीजिए हमें तीन कार्य दिए गए हैं और पूर्वापेक्षाएं [[1, 0], [2, 1], [3, 2]] हैं।

([1,0] का अर्थ है कि '1' कार्य लेने के लिए; '0' कार्य पहले पूरा किया जाना चाहिए।)

तो, इस उदाहरण में चूंकि '0' कार्य की कोई पूर्वापेक्षा नहीं है, इसे पहले पूरा किया जा सकता है। फिर '1' कार्य पूरा किया जा सकता है, क्योंकि '0' कार्य पूरा हो चुका है। इसी तरह, '2' और '3' कार्य भी पूरे किए जा सकते हैं। तो इस मामले में उत्तर "True" होगा।

इस समस्या को ग्राफ एल्गोरिदम का उपयोग करके हल किया जा सकता है। चूंकि, एरे ग्राफ एल्गोरिदम के साथ सुविधाजनक नहीं हैं, हम इसे एक ग्राफ में बदल देंगे। यह 'm' कार्य से 'n' कार्य तक एक किनारा बनाकर किया जा सकता है, यदि कार्य 'n' की निर्भरता 'm' के पूरा होने पर है।

एक बार ग्राफ बन जाने के बाद हम DFS का उपयोग कर सकते हैं। इसमें, हम एक विशेष नोड से शुरू कर सकते हैं और फिर उसके निकटतम नोड पर जा सकते हैं और फिर उस नोड के निकटतम नोड पर और इसी तरह। यदि हम एक नोड का सामना करते हैं जो पहले विजिट किया जा चुका है, तो एक चक्र बनता है और हम "False" लौटाएंगे। अन्यथा, एक बार जब हम एक टर्मिनल तक पहुंच जाते हैं, तो यह पैटर्न फिर से दूसरे नोड द्वारा तब तक अपनाया जाएगा जब तक ग्राफ के सभी नोड्स विजिट नहीं हो जाते। यदि सभी नोड्स तक पहुंच गए हैं, तो हम "True" लौटाएंगे।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

// सूची को ग्राफ में बदलें
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;
}

// जांचें कि क्या सभी नोड्स विजिट किए गए हैं
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;
}

// जांचें कि क्या सभी कार्य पूरे किए जा सकते हैं
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

  1. - C++ प्रोग्राम जांचने के लिए कि दिए गए ग्राफ में हैमिल्टोनियन साइकिल या पथ मौजूद है या नहीं

    एक हैमिल्टोनियन साइकिल एक हैमिल्टोनियन पथ है जैसे कि हैमिल्टोनियन पथ के अंतिम वर्टेक्स से पहले वर्टेक्स तक एक एज (ग्राफ में) है। यह एक अनडायरेक्टेड ग्राफ में एक पथ है जो ग्राफ के प्रत्येक वर्टेक्स को ठीक एक बार विजिट करता है। फंक्शन्स और उद्देश्य isSafe(): जांचता है कि क्या वर्टेक्स पहले से जोड़े

  1. - C++ प्रोग्राम: जांचें कि संख्या अभाज्य (Prime) है या नहीं

    परिचयएक अभाज्य संख्या एक पूर्ण संख्या है जो एक से बड़ी होती है और एक अभाज्य संख्या के केवल दो गुणनखंड होने चाहिए: एक और स्वयं। कुछ पहली अभाज्य संख्याएं हैं - 2, 3, 5, 7, 11, 13, 17 उदाहरण#include <iostream> using namespace std; int main() { int n = 17, i, flag = 0; for (i = 2; i <=

  1. - C++ में दिए गए निर्भरताओं से कार्यों का क्रम खोजें

    मान लीजिए हमारे पास n अलग-अलग कार्य हैं; ये कार्य 0 से n-1 तक लेबल किए गए हैं। कुछ कार्यों में पूर्वापेक्षा कार्य हो सकते हैं, इसलिए उदाहरण के लिए यदि हम कार्य 2 चुनना चाहते हैं तो हमें पहले कार्य 1 पूरा करना होगा, जिसे एक युग्म के रूप में दर्शाया गया है: [2, 1]। यदि हमारे पास कार्यों की कुल संख्या