https://www.luogu.com.cn/problem/P1967

kruskal 最大生成树 + set 启发式合并

求u到v所有的路径中最小边长的最大值

将所有边从大到小排序后贪心加边，然后合并并查集，每次当查询的两个点u和v分别分布在两个待合并的并查集的时候，说明当前的边长就是这次查询的答案。

可以对每个并查集维护一个集合，集合中保存的内容就是一个点在这个并查集中，而另一个点不在这个并查集中的询问编号

当待合并的两个并查集所维护的两个集合里面拥有相同的询问编号时，就可以存一下这个询问编号对应的答案，即当前这个边长
然后将小的集中没有被处理的询问编号往大的集合合并

时间复杂度 $O(n\log{n}\log{n})$

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, INF = 0x3f3f3f3f;
int n, m, fa[N], ans[3 * N];
set<int> st[N];
int find(int x) {
  return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
struct Edge {
  int u, v, w;
  bool operator < (const Edge &rhs) const {
    return w > rhs.w; // 降序
  }
};
vector<Edge> edge;
void kruskal()
{
  for (auto [u, v, w] : edge)
  {
    int ru = find(u), rv = find(v);
    if (ru == rv)
      continue;
    // 小集合往大集合合并，速度会更快一些 不然会TLE
    if (st[ru].size() > st[rv].size())
      swap(ru, rv);
    for (auto id : st[ru])
    {
      if (st[rv].count(id)) {
        ans[id] = w;
      }
      else
        st[rv].insert(id); // 只合并没处理的询问编号
    }
    st[ru].clear();
    fa[ru] = rv;
  }
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
    fa[i] = i;
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    edge.push_back({u, v, w});
  }
  sort(edge.begin(), edge.end());
  int q;
  cin >> q;
  for (int i = 1, u, v; i <= q; i++)
  {
    ans[i] = -1;
    cin >> u >> v;
    st[u].insert(i);
    st[v].insert(i);
  }
  kruskal();

  for (int i = 1; i <= q; i++)
    cout << ans[i] << endl;
  return 0;

}