C++ में भारित पथ वाले ग्राफ़ में सत्य प्रश्नों की संख्या गिनने का कार्यक्रम

मान लीजिए कि हमारे पास एक अप्रत्यक्ष ग्राफ के लिए किनारे की सूची है जहां प्रत्येक किनारे में [यू, वी, डब्ल्यू] फ़ील्ड हैं, यू और वी स्रोत और गंतव्य शिखर हैं और डब्ल्यू वजन है। और उसी फॉर्म [यू, वी, डब्ल्यू] के प्रश्नों की एक सूची भी है। यह इस प्रश्न का प्रतिनिधित्व करता है कि क्या u और v के बीच कोई पथ मौजूद है जैसे कि पथ के प्रत्येक किनारे का भार अधिकतम w है। तो उन प्रश्नों की संख्या ज्ञात करें जो सत्य हैं।

इसलिए, यदि इनपुट किनारों की तरह है =[[0, 1, 6], [1, 2, 7], [2, 3, 8], [0, 3, 5]] प्रश्न =[[0, 2, 14],[1, 0, 3]]

तो आउटपुट 1 होगा, क्योंकि हम वजन 13 के साथ इस पथ [0, 1, 2] का अनुसरण करके नोड 0 से 2 तक जा सकते हैं। लेकिन किनारे के वजन के साथ 1 से 0 तक कोई रास्ता नहीं है।

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

• एक फ़ंक्शन को परिभाषित करें get_parent(), यह x, एक सरणी सममूल्य लेगा,
• यदि par[x] x नहीं है, तो
  • बराबर[x] :=get_parent(par[x], par)
• रिटर्न पार[x]
• मुख्य विधि से निम्न कार्य करें -
• एक 2डी सरणी जीआर परिभाषित करें
• n :=0
• किनारों में प्रत्येक किनारे t के लिए −
  • n :=अधिकतम n, t[0] और t[1]
  • एक पंक्ति डालें [t[2], 0, t[0], t[1]] gr में
• प्रश्नों में प्रत्येक प्रश्न t के लिए −
  • एक पंक्ति डालें [t[2], 1, t[0], t[1]] gr में
• सॉर्ट जीआर
• आकार n + 1 के सरणी बराबर को परिभाषित करें और -1 से भरें
• इनिशियलाइज़ i :=0 के लिए, जब i <=n, अपडेट करें (i को 1 से बढ़ाएँ), −
  करें
  • बराबर[i] :=मैं
• sz :=प्रश्नों का आकार
• उत्तर:=0
• ग्र में प्रत्येक पंक्ति टी के लिए
  • ए:=टी[2], बी:=टी[3], टीपी:=टी[1], डी:=टी[0]
  • px :=get_parent(a, par)
  • py :=get_parent(b, par)
  • यदि tp, 0 के समान है, तो −
    • यदि px, py के बराबर नहीं है, तो −
      • बराबर[py] :=px
  • अन्यथा
    • यदि px, py के समान है, तो −
      • (उत्तर 1 से बढ़ाएं)
    • (sz को 1 से घटाएं)
    • यदि sz 0 के समान है, तो −
      • लूप से बाहर आएं
• वापसी उत्तर

उदाहरण (C++)

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

#include <bits/stdc++.h>
using namespace std;
int get_parent(int x, vector<int>& par) {
   if (par[x] != x) {
      par[x] = get_parent(par[x], par);
   }
   return par[x];
}
int solve(vector<vector<int>>& edges, vector<vector<int>>& queries) {
   vector<vector<int>> gr;
   int n = 0;
   for (auto t : edges) {
      n = max(n, max(t[0], t[1]));
      gr.push_back({t[2], 0, t[0], t[1]});
   }
   for (auto t : queries) {
      gr.push_back({t[2], 1, t[0], t[1]});
   }
   sort(gr.begin(), gr.end());
   vector<int> par(n + 1, -1);
   for (int i = 0; i <= n; i++) {
      par[i] = i;
   }
   int sz = queries.size();
   int ans = 0;
   for (auto t : gr) {
      int a = t[2];
      int b = t[3];
      int tp = t[1];
      int d = t[0];
      int px = get_parent(a, par);
      int py = get_parent(b, par);
      if (tp == 0) {
         if (px != py) {
            par[py] = px;
         }
      }else {
         if (px == py) {
            ans++;
         }
         sz--;
         if(sz == 0) {
            break;
         }
      }
   }
   return ans;
}
int main(){
   vector<vector<int>> edges = {{0, 1, 6},{1, 2, 7},{2, 3, 8},{0, 3, 5}};
   vector<vector<int>> queries = {{0, 2, 14},{1, 0, 3}};
   cout << solve(edges, queries);
}

इनपुट

{{0, 1, 6},{1, 2, 7},{2, 3, 8},{0, 3, 5}}, {{0, 2, 14},{1, 0, 3}}

आउटपुट

1