C++ এ ওয়েটেড পাথ সহ একটি গ্রাফে সত্য প্রশ্নগুলির সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের একটি অনির্দেশিত গ্রাফের জন্য একটি প্রান্ত তালিকা রয়েছে যেখানে প্রতিটি প্রান্তে [u, v, w] ক্ষেত্র রয়েছে, u এবং v হল উৎস এবং গন্তব্য শীর্ষবিন্দু এবং w হল ওজন। এবং একই ফর্ম [u, v, w] এর প্রশ্নের একটি তালিকা আছে। এটি এই প্রশ্নের প্রতিনিধিত্ব করে যে u এবং v এর মধ্যে এমন একটি পথ রয়েছে যে পথের প্রতিটি প্রান্তের ওজন সর্বাধিক w হয়। তাই সঠিক প্রশ্নগুলির সংখ্যা খুঁজে বের করুন।

সুতরাং, যদি ইনপুটটি প্রান্তের মত হয় =[[0, 1, 6],[1, 2, 7],[2, 3, 8],[0, 3, 5]] প্রশ্নগুলি =[[0, 2, 14],[1, 0, 3]]

তাহলে আউটপুট হবে 1, কারণ আমরা এই পথ [0, 1, 2] অনুসরণ করে নোড 0 থেকে 2 পর্যন্ত যেতে পারি ওজন 13 সহ। কিন্তু প্রান্ত ওজন 3 সহ 1 থেকে 0 পর্যন্ত কোনো পথ নেই।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

একটি ফাংশন get_parent() সংজ্ঞায়িত করুন, এটি x, একটি অ্যারে par,
যদি par[x] x না হয়, তাহলে
- par[x] :=get_parent(par[x], par)
রিটার্ন par[x]
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
একটি 2D অ্যারে gr সংজ্ঞায়িত করুন
n :=0
প্রত্যেক প্রান্তের জন্য t প্রান্তে −
- n :=সর্বাধিক n, t[0] এবং t[1]
- জিআর-এ একটি সারি [t[2], 0, t[0], t[1]] ঢোকান
প্রত্যেকটি প্রশ্নের জন্য t প্রশ্নে −
- জিআর-এ একটি সারি [t[2], 1, t[0], t[1]] ঢোকান
সর্ট gr
আকার n + 1 এর একটি অ্যারের সমাহার সংজ্ঞায়িত করুন এবং -1 দিয়ে পূরণ করুন
আরম্ভ করার জন্য i :=0, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), −
- পার[i] :=i
sz :=প্রশ্নের আকার
উত্তর :=0
gr
- a :=t[2], b :=t[3], tp :=t[1], d :=t[0]
- px :=get_parent(a, par)
- py :=get_parent(b, par)
- যদি tp 0 এর মত হয়, তাহলে −
  - যদি px py এর সমান না হয়, তাহলে −
    - par[py] :=px
- অন্যথায়
  - যদি px py এর মত হয়, তাহলে −
    - (উত্তর 1 দ্বারা বৃদ্ধি করুন)
  - (1 দ্বারা sz কমিয়ে দিন)
  - যদি 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}}