Solução: MST + 1

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