Solução: MST + 1

Dado um grafo não direcionado com pesos, de $N$ vértices e $M$ arestas, você deve responder $Q$ consultas independentes: se uma aresta entre $u_i$ e $v_i$ de peso $w_i$ fosse adicionada ao grafo, ela faria parte de sua MST?

A primeira ideia que vem à mente é, para cada pergunta, adicionar a aresta ao grafo, computar a MST e checar se ela está contida. Isso, porém, não passa dentro dos limites, tendo complexidade $\mathcal{O}(QMlogM)$ . Entretanto, percebe-se que pouco se altera no nosso algoritmo de uma consulta para outra (elas são independentes, não cumulativas), isto é, estamos fazendo a mesma coisa repetidas vezes.

De fato, as únicas informações que realmente importam são: o momento em que a aresta seria processada (sua posição na ordenação) e se $u_i$ e $v_i$ já estariam na mesma componente nesse tempo.

Isso nos traz uma outra ideia, fazer uma line sweep! Podemos ordenar todas as arestas juntas, diferenciando elas (nossos “eventos” da sweep) de alguma maneira (no código abaixo, as arestas do grafo têm “tipo” 1 e as de consultas têm “tipo” 2). Se for uma aresta do grafo em si, basta juntar os dois vértices; caso for uma consulta, deve-se checar se os dois vértices já estão na mesma componente (se estiverem, essa aresta não faria parte da MST).

Segue o código para melhor compreensão:

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

	const int MAXN = 2e5 + 10;
	const int MAXQ = 2e5 + 10;

	int n, m, q;
	int pai[MAXN], sze[MAXN];
	bool resp[MAXQ];

	struct Event
	{
	int peso, tipo, id, u, v;
	// tipo 1: aresta do grafo, tipo 2: aresta de consulta

	Event(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) :
	peso(a), tipo(b), id(c), u(d), v(e) { }

	bool operator < (Event other){ return peso < other.peso; }
	};

	int find(int u)
	{
	return pai[u] = (pai[u] == u ? u : find(pai[u]));
	}

	void join(int u, int v)
	{
	u = find(u), v = find(v);
	if(u == v) return;

	if(sze[u] < sze[v]) swap(u, v);
	sze[u] += sze[v]; pai[v] = u;
	}

	int main()
	{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	vector<Event> arestas;

	cin >> n >> m >> q;

	for(int i = 1; i <= m; i++){
	int u, v, w; cin >> u >> v >> w;
	arestas.emplace_back(w, 1, -1, u, v);
	}

	for(int i = 1; i <= q; i++){
	int u, v, w; cin >> u >> v >> w;
	arestas.emplace_back(w, 2, i, u, v);
	}

	// Ordeno as arestas todas juntas
	sort(arestas.begin(), arestas.end());

	// Inicializo a DSU
	iota(pai + 1, pai + 1 + n, 1);
	fill(sze + 1, sze + 1 + n, 1);

	for(auto [w, type, id, u, v] : arestas){
	if(type == 1) join(u, v);
	else resp[id] = (find(u) != find(v));
	}

	for(int i = 1; i <= q; i++)
	cout << (resp[i] ? "Yes" : "No") << '\n';
	}

view raw

mst.cpp

hosted with ❤ by GitHub

Outra Solução:

Poderíamos responder às queries de forma online utilizando a técnica de DSU semi-persistente para achar o tempo em que os dois vértices passariam a estar na mesma componente. Deve-se retirar o path compression e inserir o “tempo” em que dois vértices foram ligados na aresta entre eles. Agora para achar o momento em que passaram a estar na mesma componente, basta ir subindo na árvore da DSU até chegar ao LCA. Segue o código dessa ideia:

	#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';
	}
	}

view raw

mst2.cpp

hosted with ❤ by GitHub