前置知识点：Kruskal算法
详细讲解：Kruskal算法简易教程（附最全注释代码实现）_kruskal算法测试实例-CSDN博客
环游小岛
这是一个关于小岛环游的考验。在这个考验中，有n座小岛分布在海洋中，小岛与小岛之间的距离有近有远。为了到达不同的小岛，你可以选择游泳或者搭乘快艇。
现给出m对小岛之间的距离，距离用 w 来表示你可以通过消耗 w 的体力值从其中一个小岛到达另一个小岛。这个体力值可以是正值，代表需要消耗体力游泳到达；也可以是负值，代表可以搭乘快艇轻松到达。换句话说，正值表示需要付出额外的努力，而负值则表示可以省下体力。
在这个环游计划中，你可以选择在任意一座小岛上休息，休息的时间没有限制。这样可以恢复体力，并为接下来的旅程做好准备。
现在给出了 q 个询问，每个询问包含三个信息：起点、终点和你当前的体力值上限。问题是，能否凭借当前的体力值上限完成从起点到终点的环游计划。
输入格式：
第一行包含两个整数n、m、q ，
接下来 m 行，每行包含三个整数x、y、w，w 代表 x 和 y 两个小岛间的距离，
接下来 q 行，每行包含三个整数x、y、t，问是否能够凭借体力值上限 t 完成从 x 到 y 的环游计划。
1<=n<=1e5，1<=m<=1e5，1<=q<=1e5
1<=x,y<=n，0<=∣w∣<=1e9，0<=t<=1e9
输出格式：
共 q 行，每行根据询问给出答案，若可以完成该询问的环游计划则输出 YES ，反之则输出 NO 。
输入样例：
3 3 3
1 2 1
2 3 2
1 3 3
1 3 2
1 2 0
2 3 1
输出样例：
YES
NO
NO思路：Kruskal算法+并查集--通过对每条边的升序排列，从这条边可以走出的最小生成图，通过并查集来判断查询的起，终点是否在一个集合内
//Kruskal
//概论：通过对每条边的升序排列，从这条边可以走出的最小生成图来判断查询是否可靠
//内涵迭代思想
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7, inf = 0x3f3f3f3f, mod = 1e9+7, eps = 1e-9;
int fa[N], ans[N];
vector<array<int, 3>> edge;
int find(int x){
if(fa[x] != x) fa[x] = find(fa[x]);
return fa[x];
}
int main(){
int n, m, q; cin >> n >> m >> q;
for(int i = 1; i <= n; ++i) fa[i] = i; //初始化
for(int i = 0; i < m; ++i){
int x, y, w; cin >> x >> y >> w;
edge.push_back({w, x, y});
}
sort(edge.begin(), edge.end()); //体力升序排序
vector<array<int,4>> ask;
for(int i = 0; i < q; ++i){
int x, y, t; cin >> x >> y >> t;
ask.push_back({t, x, y, i});
}
sort(ask.begin(), ask.end());
int now = 0;
for(auto [w, x, y] : edge){ //对每一条边
while(now < ask.size() && w > ask[now][0]){ //当前体力大于需要的体力
auto [t, st, ed, idx] = ask[now];
if(find(st) == find(ed)) ans[idx] = 1; //如果节点已连接，YES
now++;
}
fa[find(x)] = find(y);
}
for(int i = now; i < ask.size(); ++i){
auto [t, st, ed, idx] = ask[i];
if(find(st) == find(ed)) ans[idx] = 1;
}
for(int i = 0; i < q; ++i)
if(ans[i]) cout << "YES\n";
else cout << "NO\n";
return 0;
}
