Kruskal + 并查集 求调

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

const int _ = 1e5 + 1;
//int maxx=INT_MIN;
struct Edge
{
	int u, v, w;
} b[_];

bool cmp(Edge a, Edge b)
{
	return a.w < b.w;
}

int fa[_];

int __find(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = __find(fa[x]);
}

signed main()
{
	int n, m, s, t;
	cin >> n >> m >> s >> t;

	for (int i = 1; i <= n; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		b[i].u = u, b[i].v = v, b[i].w = w;
//		__union(u, v);
	}

	sort(b + 1, b + 1 + m, cmp);

	for (int i = 1; i <= m; i++)
	{
		int fx = __find(b[i].u), fy = __find(b[i].v);

		if (fx == fy) continue;
		
		if (__find(s) == __find(t)) return cout << b[i].w << endl, 0;
		
	}
	return 0;
}