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

दिए गए शर्त के साथ ग्राफ में अधिकतम संभव विभाजन गिनने के लिए C++ प्रोग्राम


मान लीजिए हमारे पास एक ग्राफ G का आसन्नता मैट्रिक्स है। हमें जांचना है कि क्या हम शीर्षों को गैर-खाली सेट V1, ... Vk में विभाजित कर सकते हैं, जैसे कि: प्रत्येक किनारा दो शीर्षों को जोड़ता है जो दो आसन्न सेट से संबंधित हैं। यदि उत्तर हां है, तो हमें ऐसे विभाजन में सेट k का अधिकतम संभव मान ढूंढना है।

उदाहरण के लिए, यदि इनपुट है:

0 1 0 1 1 0
1 0 1 0 0 1
0 1 0 1 0 0
1 0 1 0 0 0
1 0 0 0 0 0
0 1 0 0 0 0

तो आउटपुट 4 होगा

चरण

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

आकार 210 का एक ऐरे dp परिभाषित करें n := मैट्रिक्स का आकार fl := 1 ans := 0 i := 0 से n-1 तक और fl शून्येतर होने तक, करें: dp को -1 से भरें dp[i] := 0 एक कतार q परिभाषित करें i को q में डालें जब तक (q खाली नहीं है), करें: x := q का पहला तत्व q से तत्व हटाएं j := 0 से n-1 तक, करें: यदि matrix[x, j], 1 के बराबर है, तो: यदि dp[j], -1 के बराबर है, तो: dp[j] := dp[x] + 1 j को q में डालें अन्यथा जब |dp[j] - dp[x]|, 1 के बराबर नहीं है, तो: fl := 0 j := 0 से n-1 तक, करें: ans := ans और dp[j] का अधिकतम यदि fl, 0 के बराबर है, तो: -1 वापस करें अन्यथा ans + 1 वापस करें

उदाहरण

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

#include <bits/stdc++.h> using namespace std; int solve(vector<vector<int>> matrix){    int dp[210];    int n = matrix.size();    int fl = 1;    int ans = 0;    for (int i = 0; i < n && fl; i++){       memset(dp, -1, sizeof(dp));       dp[i] = 0;       queue<int> q;       q.push(i);       while (!q.empty()){          int x = q.front();          q.pop();          for (int j = 0; j < n; j++){             if (matrix[x][j] == 1){                if (dp[j] == -1){                   dp[j] = dp[x] + 1;                   q.push(j);                }                else if (abs(dp[j] - dp[x]) != 1)                   fl = 0;             }          }       }       for (int j = 0; j < n; j++)          ans = max(ans, dp[j]);    }    if (fl == 0){       return -1;    }else{       return ans + 1;    } } int main(){    vector<vector<int>> matrix = { { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } };    cout << solve(matrix) << endl; }

इनपुट

{ { 0, 1, 0, 1, 1, 0 }, { 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0 }, { 1, 0, 0, 0, 0, 0 }, { 0, 1, 0, 0, 0, 0 } }

आउटपुट

4

  1. आकार d के डोडेकागन बनाने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम आकार d के डोडेकागन बनाने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम

    मान लीजिए हमारे पास एक संख्या d है। मान लें कि भुजा लंबाई 1 के अनंत वर्गाकार टाइल्स और नियमित त्रिकोणीय टाइल्स हैं। हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम इन टाइल्स का उपयोग करके भुजा d के साथ नियमित डोडेकागन (12-भुज बहुभुज) बना सकते हैं। यदि उत्तर बहुत बड़ा है, तो परिणाम को 998244353 मॉड्यूलो

  1. - दो शर्तों के साथ ब्लॉकों को पेंट करने के तरीकों की संख्या गिनने के लिए C++ प्रोग्राम

    मान लीजिए हमारे पास तीन संख्याएं N, M और K हैं। मान लें N ब्लॉक हैं जो एक पंक्ति में व्यवस्थित हैं। हम उन्हें पेंट करने के निम्नलिखित दो तरीकों पर विचार करते हैं। दो ब्लॉकों के पेंट तभी अलग माने जाते हैं जब ब्लॉकों को निम्नलिखित दो तरीकों से अलग-अलग रंगों से रंगा जाता है: प्रत्येक ब्लॉक के लिए, इसे

  1. कुछ शर्तों के साथ ग्राफ बनाने के लिए C++ प्रोग्राम कुछ शर्तों के साथ ग्राफ बनाने के लिए C++ प्रोग्राम

    मान लीजिए हमारे पास दो संख्याएं N और K हैं। N तत्वों वाला एक निदेशित ग्राफ पर विचार करें। N शीर्ष निम्नलिखित शर्तों को पूरा करते हैं: ग्राफ सरल और जुड़ा हुआ है शीर्ष 1 से N तक गिने जाते हैं मान लें M ग्राफ में किनारों की संख्या है। किनारों को 1 से M तक गिना जाता है। किनारे की लंबाई 1 है। और किनारा