Solução: MST + 1
Dado um grafo não direcionado com pesos, de vértices e arestas, você deve responder consultas independentes: se uma aresta entre e de peso 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 . 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 e 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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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'; | |
} | |
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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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'; | |
} | |
} |