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

C++ में दो अलग-अलग अच्छे नोड्स के किसी भी जोड़े के बीच सबसे कम दूरी ज्ञात करें

मान लीजिए कि हमारे पास एन अलग-अलग नोड्स और एम किनारों के साथ एक भारित अप्रत्यक्ष ग्राफ है, कुछ नोड्स अच्छे नोड्स हैं। हमें दो अलग-अलग अच्छे नोड्स के किसी भी जोड़े के बीच सबसे छोटी दूरी का पता लगाना है। दिए गए आरेख में निम्नलिखित ग्राफ में पीले रंग को अच्छा नोड माना जाता है।

तो, अगर इनपुट पसंद है

C++ में दो अलग-अलग अच्छे नोड्स के किसी भी जोड़े के बीच सबसे कम दूरी ज्ञात करें

तो आउटपुट 11 होगा, क्योंकि अच्छे नोड्स के जोड़े और उनके बीच की दूरी है:(1 से 3) दूरी 11 है, (3 से 5) दूरी 13 है, (1 से 5) दूरी 24 है, बाहर जिनमें से 11 न्यूनतम है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • एन:=100005

  • MAX_VAL :=99999999

  • एक प्राथमिकता कतार बनाएं q

  • परिणाम:=MAX_VAL

  • इनिशियलाइज़ i :=1 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), करें -

    • अगर good_verts[i] गलत है, तो -

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • इनिशियलाइज़ j :=1 के लिए, जब j <=n, अपडेट करें (j को 1 से बढ़ाएँ), करें -

      • जिला [जे] :=MAX_VAL

      • विज़ [जे]:=0

    • जिला [i] :=0

    • जबकि (नहीं q खाली है), करें -

      • q से तत्व हटाएं

    • q में { 0, i } डालें

    • अच्छा :=0

    • जबकि (नहीं q खाली है), करें -

      • v:=q का शीर्ष तत्व

      • q से तत्व हटाएं

      • अगर vis[v] सत्य है, तो -

        • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

      • विज़ [v] :=1

      • अच्छा :=अच्छा + (1 जब good_verts[v] सत्य है, अन्यथा 0)

      • अगर dist[v]> परिणाम, तो -

        • लूप से बाहर आएं

      • अगर अच्छा 2 और good_verts[v] के समान है, तो -

        • परिणाम :=न्यूनतम परिणाम और जिला[v]

        • लूप से बाहर आएं

      • इनिशियलाइज़ j :=0 के लिए, जब j <ग्राफ़ का आकार[v], अपडेट करें (1 से j बढ़ाएँ), करें -

        • से :=ग्राफ़[v, j].पहले

        • वजन:=ग्राफ[v, j].सेकंड

        • यदि जिला [v] + वजन <जिला [से], तो -

          • जिला [से]:=जिला [वी] + वजन

          • q में { dist[to], to } डालें q

  • वापसी परिणाम

उदाहरण

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

#include <bits/stdc++.h>
using namespace std;
#define N 100005
#define MAX_VAL 99999999
void insert_edge(vector<pair<int, int> > graph[], int x, int y, int weight) {
   graph[x].push_back({ y, weight });
   graph[y].push_back({ x, weight });
}
int get_min_dist(vector<pair<int, int> > graph[], int n, int dist[], int vis[], int good_verts[], int k) {
   priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>> q;
   int result = MAX_VAL;
   for (int i = 1; i <= n; i++) {
      if (!good_verts[i])
         continue;
      for (int j = 1; j <= n; j++) {
         dist[j] = MAX_VAL;
         vis[j] = 0;
      }
      dist[i] = 0;
      while (!q.empty())
      q.pop();
      q.push({ 0, i });
      int good = 0;
      while (!q.empty()) {
         int v = q.top().second;
         q.pop();
         if (vis[v])
         continue;
         vis[v] = 1;
         good += good_verts[v];
         if (dist[v] > result)
            break;
         if (good == 2 and good_verts[v]) {
            result = min(result, dist[v]);
            break;
         }
         for (int j = 0; j < graph[v].size(); j++) {
            int to = graph[v][j].first;
            int weight = graph[v][j].second;
            if (dist[v] + weight < dist[to]) {
               dist[to] = dist[v] + weight;
               q.push({ dist[to], to });
            }
         }
      }
   }
   return result;
}
int main() {
   int n = 5, m = 5;
   vector<pair<int, int> > graph[N];
   insert_edge(graph, 1, 2, 3);
   insert_edge(graph, 1, 2, 3);
   insert_edge(graph, 2, 3, 4);
   insert_edge(graph, 3, 4, 1);
   insert_edge(graph, 4, 5, 8);
   int k = 3;
   int good_verts[N], vis[N], dist[N];
   good_verts[1] = good_verts[3] = good_verts[5] = 1;
   cout << get_min_dist(graph, n, dist, vis, good_verts, k);
}

इनपुट

n = 5, m = 5
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 1, 2, 3);
insert_edge(graph, 2, 3, 4);
insert_edge(graph, 3, 4, 1);
insert_edge(graph, 4, 5, 8);
k = 3
good_verts[1] = good_verts[3] = good_verts[5] = 1;

आउटपुट

7

  1. C++ में किसी बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ का XOR

    इस समस्या में हमें एक बाइनरी ट्री और बाइनरी ट्री के दो नोड दिए जाते हैं। हमारा काम दो नोड्स के बीच के रास्ते में आने वाले सभी नोड्स के XOR को प्रिंट करना है। समस्या को समझने के लिए एक उदाहरण लेते हैं, हमें 2 और 3 के बीच के सभी नोड्स के xor को खोजने की जरूरत है। 2 से 3 तक का रास्ता, 2 → 6 → 1 →

  1. C++ में एक बाइनरी ट्री के दो नोड्स के बीच की दूरी का पता लगाएं

    मान लें कि हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें दो नोड्स u और v के बीच की दूरी ज्ञात करनी है। मान लीजिए कि पेड़ नीचे जैसा है - अब (4, 6) =4 के बीच की दूरी, पथ की लंबाई 4 है, (5, 8) के बीच की लंबाई =5 आदि। इस समस्या को हल करने के लिए, हम एलसीए (सबसे कम सामान्य पूर्वज) ढूंढेंगे, फिर

  1. C++ प्रोग्रामिंग में बाइनरी ट्री में किन्हीं दो नोड्स के बीच प्रिंट पथ।

    हमें अलग-अलग नोड्स के एक बाइनरी ट्री और बाइनरी ट्री के दो नोड्स दिए गए हैं, जिसका बाइनरी ट्री में पथ हम प्रिंट करना चाहते हैं। उदाहरण के लिए - हम नोड 140 से 211 के बीच के पाथ को प्रिंट करना चाहते हैं, इसलिए इसका आउटपुट इस तरह होना चाहिए - Output: 140->3->10->211 विचार दो नोड्स के लिए रू