โปรแกรมนับคำถามที่เป็นจริงในกราฟมีน้ำหนักขอบใน C++

ให้กราฟไม่มีทิศทาง edges=[u,v,w] และ queries=[u,v,w] คำถาม: มี path จาก u ถึง v ที่น้ำหนักทุกขอบ <= w หรือไหม นับคำถามที่เป็นจริง

ตัวอย่าง: edges=[[0,1,6],[1,2,7],[2,3,8],[0,3,5]], queries=[[0,2,14],[1,0,3]] → 1 0→2: path 0-1-2 น้ำหนัก max=7 <=14 ✓, 1→0: ต้องใช้ 0-1 (6) > 3 ✗

ขั้นตอนการแก้ปัญหา (Offline + DSU)

1. รวม edges และ queries เข้าด้วยกัน พร้อม tag type (0=edge, 1=query)
2. เรียงตามน้ำหนัก w น้อยไปมาก
3. ใช้ DSU (Disjoint Set Union) เชื่อมโหนด
4. วนตามลำดับ:
   • ถ้า edge: union(u,v)
   • ถ้า query: ถ้า find(u)==find(v) → ans++

เพราะเราประมวลผลตามน้ำหนักเพิ่มขึ้น เมื่อถึง query w ทุก edge <= w ถูก union แล้ว

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

int get_parent(int x, vector<int>& par) {
    return par[x] == x ? x : par[x] = get_parent(par[x], par);
}

int solve(vector<vector<int>>& edges, vector<vector<int>>& queries) {
    vector<vector<int>> all;
    int n = 0;
    for (auto& e : edges) {
        n = max(n, max(e[0], e[1]));
        all.push_back({e[2], 0, e[0], e[1]});
    }
    for (auto& q : queries)
        all.push_back({q[2], 1, q[0], q[1]});
    
    sort(all.begin(), all.end());
    vector<int> par(n+1);
    iota(par.begin(), par.end(), 0);
    
    int ans = 0, rem = queries.size();
    for (auto& t : all) {
        int w = t[0], type = t[1], u = t[2], v = t[3];
        int pu = get_parent(u, par), pv = get_parent(v, par);
        if (type == 0) {
            if (pu != pv) par[pv] = pu;
        } else {
            if (pu == pv) ans++;
            if (--rem == 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); // 1
    return 0;
}

อินพุต

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

เอาต์พุต

1