समस्या विवरण
मान लीजिए हमारे पास एक अनडायरेक्टेड ग्राफ के लिए एज लिस्ट है जहां प्रत्येक एज में [u, v, w] फील्ड होते हैं, u और v स्रोत और गंतव्य वर्टेक्स हैं और w वजन है। और क्वेरीज की एक सूची भी उसी फॉर्म [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 होगा, क्योंकि हम नोड 0 से 2 तक इस पथ [0, 1, 2] का अनुसरण करके वजन 13 के साथ जा सकते हैं। लेकिन 1 से 0 तक एज वजन 3 के साथ कोई पथ नहीं है।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम यूनियन-फाइंड (डिसजॉइंट सेट यूनियन) का उपयोग करेंगे:
- एक फंक्शन get_parent() परिभाषित करें जो x और par ऐरे लेता है
- यदि par[x] != x, तो par[x] := get_parent(par[x], par)
- par[x] वापस करें
- मुख्य विधि से:
- एक 2D ऐरे gr परिभाषित करें
- n := 0
- edges में प्रत्येक एज t के लिए:
- n := max(n, t[0], t[1])
- gr में [t[2], 0, t[0], t[1]] पंक्ति डालें
- queries में प्रत्येक क्वेरी t के लिए:
- gr में [t[2], 1, t[0], t[1]] पंक्ति डालें
- gr को सॉर्ट करें
- आकार n+1 का एक ऐरे par परिभाषित करें और -1 से भरें
- i := 0 से n तक: par[i] := i
- sz := queries का आकार
- ans := 0
- gr में प्रत्येक पंक्ति t के लिए:
- 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, तो ans बढ़ाएं
- sz घटाएं
- यदि sz == 0, तो लूप से बाहर निकलें
- ans वापस करें
उदाहरण
#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