MST + 1 com DSU

mst2.cpp

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

const int MAX = 2e6 + 15;
const int INF = 0x3f3f3f3f;
 
int n, m, q;
tuple<int, int, int> edges[MAX];
 
int pai[MAX], sze[MAX], edge[MAX], timer;
 
int find(int u)
{
	return (pai[u] == u ? u : find(pai[u]));
}
 
void join(int u, int v)
{
	u = find(u), v = find(v); timer++;
	if(u == v) return;
 
	if(sze[u] < sze[v]) swap(u, v);
 
	pai[v] = u;
	edge[v] = timer; // peso da aresta

	sze[u] += sze[v];
}
 
int query(int u, int v) // retorna o tempo em que passaram a estar na mesma componente
{ 
	int resp = 0;
 
	while(u != v){
		if(edge[u] < edge[v]){ resp = edge[u]; u = pai[u]; }
		else{ resp = edge[v]; v = pai[v]; }
	}
 
	return resp;
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> n >> m >> q;
 	
 	// Inicializar a DSU
	iota(pai + 1, pai + 1 + n, 1);		
	fill(sze + 1, sze + 1 + n, 1);
	fill(edge + 1, edge + 1 + n, INF);
 
	for(int i = 1; i <= m; i++){
		auto &[w, u, v] = edges[i];
		cin >> u >> v >> w;
	}

	// Faco o kruskal, considerando as m arestas originais
	sort(edges + 1, edges + 1 + m);

	for(int i = 1; i <= m; i++){
	    auto [w, u, v] = edges[i]; 
	    join(u, v);
	}
 
	while(q--){
		int u, v, w; cin >> u >> v >> w;
		int l = 1, r = m, opt = 0;
 
 		// Busca Binaria
		while(l <= r){
			int mid = (l + r) >> 1;
			if(get<0>(edges[mid]) < w) opt = mid, l = mid + 1;
			else r = mid - 1;
		}
 
		cout << (query(u, v) <= opt ? "No" : "Yes") << '\n';
	}
}