সি++-এ ওয়েইটেড পাথ কোয়েরি দিয়ে গ্রাফে সত্য কোয়েরি সংখ্যা গণনা

সমস্যা বিবরণ

একটি আনডিরেক্টেড গ্রাফের এজ লিস্ট [u, v, w] দেওয়া আছে। Qটি কোয়েরি [u, v, w] দেওয়া আছে। প্রতিটি কোয়েরি জিজ্ঞাসা করে: u থেকে v-এ এমন পাথ আছে কিনা যাতে পাথের সব এজর ওয়েইট w বা তার কম। সত্য কোয়েরির সংখ্যা বের করতে হবে।

উদাহরণ: edges = [[0,1,6],[1,2,7],[2,3,8],[0,3,5]], queries = [[0,2,14],[1,0,3]] → আউটপুট 1।

সমাধানের পদ্ধতি

অফলাইন প্রসেসিং + ডিজয়েন্ট সেট ইউনিয়ন (DSU):

1. এজ ও কোয়েরি দুটোকেই একসাথে সর্ট করুন ওয়েইট অনুযায়ী।
2. DSU ইনিশিয়ালাইজ করুন।
3. সর্টেড লিস্ট ট্রভার্স করুন:
   • যদি এজ হয়: union(u, v) করুন।
   • যদি কোয়েরি হয়: চেক করুন find(u) == find(v)। হলে আন্সার বাড়ান।
4. এভাবে ছোট ওয়েইটের এজগুলো আগে যুক্ত হয়, বড় ওয়েইটের কোয়েরি সময়ে কানেক্টেড কম্পোনেন্ট চেক করা যায়।

উদাহরণ কোড

#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);
    iota(par.begin(), par.end(), 0);
    int sz = queries.size(), ans = 0;
    for (auto t : gr) {
        int a = t[2], b = t[3], tp = t[1], d = t[0];
        int px = get_parent(a, par), py = get_parent(b, par);
        if (tp == 0) {
            if (px != py) par[py] = px;
        } else {
            if (px == py) ans++;
            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);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: edges={{0,1,6},{1,2,7},{2,3,8},{0,3,5}}, queries={{0,2,14},{1,0,3}}

আউটপুট: 1